信息学奥赛一本通 ybt 1933：【05NOIP普及组】循环 | 洛谷 P1050 [NOIP2005 普及组] 循环

【题目链接】

ybt 1933：【05NOIP普及组】循环
洛谷 P1050 [NOIP2005 普及组] 循环

【题目考点】

1.高精度

2.数学

【解题思路】

要求最后k位的循环长度，可以从低位向高位看。
假设n的最后k位为$d_k{d}_{k-1}...d_2{d}_1$

• 先看最低位$d_1$，假设$d_1^{l_1}$的最后一位位是$d_1$，它的循环长度为$l_1$
• 然后看倒数两位$d_2{d}_1$，以$(d_2{d}_1{)}^{l_1}$为单位进行累乘，可以保证结果的个位是$d_1$，假设累乘$l_2$次，$(d_2{d}_1{)}^{l_1{l}_2}$的倒数第2位是$d_2$，即末两位是$d_2{d}_1$，循环长度为$l_1{l}_2$
• 然后看倒数3位$d_3{d}_2{d}_1$，以$(d_3{d}_2{d}_1{)}^{l_1{l}_2}$为单位进行累乘，可以保证末两位是$d_2{d}_1$，假设累乘$l_3$次后$(d_3{d}_2{d}_1{)}^{l_1{l}_2{l}_3}$的倒数第3位是$d_3$，即末3位是$d_3{d}_2{d}_1$，那么循环长度为$l_1{l}_2{l}_3$
  以此类推，直到求出倒数k位的循环长度
• 如果累乘10次后，结果的末几位与原数字仍然不同，那么就不会发生循环，输出-1。

说明：
假设现在在看倒数m位，$d_m...d_2{d}_1$，以$(d_m...d_2{d}_1{)}^{l_1{l}_2...l_{m-1}}$为单位进行累乘，可以保证最后m-1位为$d_{m-1}...d_2{d}_1$。变化的只有结果的倒数第m位，该位置可能的数字只有0~9这10种。

• 如果每次乘$(d_m...d_2{d}_1{)}^{l_1{l}_2...l_{m-1}}$得到的倒数第m位都不同，那么10次累乘中，一定至少有一次其倒数第m位的值与$d_m$相同。
• 如果10次累乘中，倒数第m位都没能等于$d_m$，说明这10次中，倒数第m位出现了重复的数字，倒数第m位数字的变化存在循环，而这个循环中没有$d_m$这个数字。所以$d_m...d_2{d}_1$不会循环出现，应该输出-1。

解法1：

严格按照上述方法执行，每次循环只看末m位，前先求累乘单位$(d_m...d_2{d}_1{)}^{l_1{l}_2...l_{m-1}}$，需要用到快速幂。

解法2：

整体思路与上述方法大体相同，不过直接取n的末k位作为累乘单位，不再分别取末1位，末2位。。。

• 先看最低位$d_1$，假设$(d_k{d}_{k-1}...d_2{d}_1{)}^{l_1}$的最后一位位是$d_1$，它的循环长度为$l_1$
• 然后看倒数两位$d_2{d}_1$，以$(d_k{d}_{k-1}...d_2{d}_1{)}^{l_1}$为单位进行累乘，可以保证结果的个位是$d_1$，假设累乘$l_2$次，$(d_k{d}_{k-1}...d_2{d}_1{)}^{l_1{l}_2}$的倒数第2位是$d_2$，即末两位是$d_2{d}_1$，循环长度为$l_1{l}_2$
• 然后看倒数3位$d_3{d}_2{d}_1$，以$(d_k{d}_{k-1}...d_2{d}_1{)}^{l_1{l}_2}$为单位进行累乘，可以保证末两位是$d_2{d}_1$，假设累乘$l_3$次后$(d_k{d}_{k-1}...d_2{d}_1{)}^{l_1{l}_2{l}_3}$的倒数第3位是$d_3$，即末3位是$d_3{d}_2{d}_1$，那么循环长度为$l_1{l}_2{l}_3$
• 如此来做，上一次循环的累乘的结果可以直接作为下一次循环的累乘单位，可以省去解法1中做快速幂的过程。

【题解代码】

代码中几个Multiply函数名字相同，参数个数或类型不同，构成函数重载，几个函数都可以被正确使用。

解法1：

#include<bits/stdc++.h> using namespace std; #define N 305 void numcpy(int a[], int b[])//b拷贝给a {for(int i = 0; i <= b[0]; ++i)//把r赋值给a a[i] = b[i]; } void Multiply(int a[], int b[], int m)//a *= b 高精乘高精 结果只取末m位 {int r[N] = {}, ri;for(int i = 1; i <= a[0]; ++i){int c = 0;for(int j = 1; j <= b[0]; ++j){r[i+j-1] += a[i]*b[j] + c;c = r[i+j-1] / 10;r[i+j-1] %= 10; }r[i+b[0]] += c;}ri = a[0] + b[0];while(r[ri] == 0 && ri > 1)ri--;r[0] = ri;if(r[0] > m)r[0] = m; numcpy(a, r); } void Multiply(int a[], int b)//a *= b 高精乘低精 {int c = 0, i;for(i = 1; i <= a[0]; ++i){a[i] = a[i]*b + c;c = a[i] / 10;a[i] %= 10; }while(c > 0){a[i] = c % 10;c /= 10;i++;}while(a[i] == 0 && i > 1)i--;a[0] = i; } void Divide(int a[], int b) //高精除低精 a/=b {int x = 0, ai;//余数 for(int i = a[0]; i >= 1; i--){x = x * 10 + a[i];a[i] = x / b;x %= b;}ai = a[0];while(a[ai] == 0 && ai > 1)ai--;a[0] = ai; } void fastPower(int a[], int b[], int m)//快速幂 a^b取末m位 ，结果保存给a {int r[N] = {1, 1}, c[N];//a为基数，c为指数，r为结果 numcpy(c, b);while(!(c[0] == 1 && c[1] == 0))//c != 0{if(c[1] % 2 == 1)//用b的个位判断其是否是偶数 Multiply(r, a, m); Multiply(a, a, m);Divide(c, 2);}numcpy(a, r); } void tonum(int a[], char s[])//字符串转为数字数组 {int len = strlen(s);for(int i = 1; i <= len; ++i)a[i] = s[len-i] - '0';a[0] = len; } void cutNum(int a[], int n, int b[])//截取数字a的后n位 赋值给数字b {for(int i = 1; i <= n; ++i)b[i] = a[i];b[0] = n; } int main() {int n[N] = {}, a[N] = {}, b[N] = {}, l[N] = {1,1}, k;//a：累乘单位 l:循环长度 初值为1 char s[N];cin >> s >> k;tonum(n, s);for(int i = 1; i <= k; ++i)//i:看后i位 {cutNum(n, i, a);//构造a为n的后i位 fastPower(a, l, i);//n的后i位累乘l次，使a成为累乘单位 cutNum(n, i, b);//构造b为n的后i位 bool isFound = false; //第i位的循环长度是否找到 for(int j = 1; j <= 10; ++j){Multiply(b, a, i);if(b[i] == n[i])//如果倒数第i位又变回为原来的倒数第i位 {Multiply(l, j);//找到第i位的循环长度为j isFound = true;break;}}if(isFound == false){//如果没找到，则不存在循环长度 cout << -1;return 0;}}for(int i = l[0]; i >= 1; i--)//输出循环长度cout << l[i]; return 0; }

解法2：

#include<bits/stdc++.h> using namespace std; #define N 305 int k;//结果取末k位 void numcpy(int a[], int b[])//b拷贝给a {for(int i = 0; i <= b[0]; ++i)//把r赋值给a a[i] = b[i]; } void Multiply(int a[], int b[], int r[])//a * b = r 高精乘高精 结果只取末k位 {for(int i = 1; i <= a[0]; ++i){int c = 0;for(int j = 1; j <= b[0]; ++j){r[i+j-1] += a[i]*b[j] + c;c = r[i+j-1] / 10;r[i+j-1] %= 10; }r[i+b[0]] += c;}int ri = a[0] + b[0];while(r[ri] == 0 && ri > 1)ri--;r[0] = ri;if(r[0] > k)r[0] = k; } void Multiply(int a[], int b[])//a *= b 高精乘高精 结果只取末k位 {int r[N] = {};Multiply(a, b, r);numcpy(a, r); } void Multiply(int a[], int b)//a *= b 高精乘低精 {int c = 0, i;for(i = 1; i <= a[0]; ++i){a[i] = a[i]*b + c;c = a[i] / 10;a[i] %= 10; }while(c > 0){a[i] = c % 10;c /= 10;i++;}while(a[i] == 0 && i > 1)i--;a[0] = i; } void tonum(int a[], char s[])//字符串转为数字数组 {int len = strlen(s);for(int i = 1; i <= len; ++i)a[i] = s[len-i] - '0';a[0] = len; } int main() {int n[N] = {}, a[N] = {}, b[N] = {}, c[N] = {}, l[N] = {1,1};//a：累乘单位 l:循环长度 初值为1 char s[N];cin >> s >> k;tonum(n, s);numcpy(a, n);//累乘单位a初值为nfor(int i = 1; i <= k; ++i)//i:看后i位 {bool isFound = false; //第i位的循环长度是否找到 c[0] = c[1] = 1;//c = 1; 累乘乘积 for(int j = 1; j <= 10; ++j){Multiply(c, a);//高精乘高精 c *= a;memset(b, 0, sizeof(b));Multiply(c, n, b);//高精乘高精 b = a*nif(b[i] == n[i])//如果倒数第i位又变回为原来的倒数第i位 {Multiply(l, j);//高精乘低精 找到第i位的循环长度为j isFound = true;break;}}if(isFound == false){//如果没找到，则不存在循环长度 cout << -1;return 0;}numcpy(a, c);//使当前c的值为下一次的累乘单位a了}for(int i = l[0]; i >= 1; i--)//输出循环长度cout << l[i]; return 0; }

总结

以上是生活随笔为你收集整理的信息学奥赛一本通 ybt 1933：【05NOIP普及组】循环 | 洛谷 P1050 [NOIP2005 普及组] 循环的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。