高数位循环节是低数位循环节的倍数。
两个不同的高精度,一个算乘法,一个保存答案(答案那程度也必是高精度弄出来的)
为了方便我自己debug,很多循环写成了一行,将就看吧……
#include <iostream>
#include <cstring>
using namespace std;
const short MAXMI = 14;//每个数位10个数,再加一个原数(1),两个乘数(12 13),一个存上个数位的数(0),共14行
short n[MAXMI][101] = {}, ans[101] = {};
int main() {
int k, len, mi, anslen = 1;
char N[101] = {};
bool p;
cin.getline(N, 101, ' ');
len = strlen(N);
cin >> k; ans[1] = 1;
for (int i = len - 1; (i >= len - k) && (i >= 0); --i) {n[1][len - i] = int(N[i]) - int('0'); n[0][len - i] = n[1][len - i]; }
for (int ki = 1; ki <= k; ++ki) {
mi = 2;
for (int i = 2; i <= k; ++i) n[12][i] = 0; n[12][1] = 1;
do {
for (int i = 1; i <= k; ++i) n[13][i] = 0;
for (int i = 1; i <= k; ++i) for (int j = 1; j <= k - i + 1; ++j) n[13][i - 1 + j] += n[12][j] * n[0][i];
for (int i = 1; i <= k; ++i) for (int j = 1; j <= k - i + 1; ++j) n[mi][i - 1 + j] += n[13][j] * n[1][i];
for (int i = 1; i <= k; ++i) n[12][i] = n[13][i];
//乘法,n[13]存的是不含原数的
for (int i = 1; i < k; ++i) {n[mi][i + 1] += n[mi][i] / 10; n[mi][i] = n[mi][i] % 10; n[12][i + 1] += n[12][i] / 10; n[12][i] = n[12][i] % 10; n[13][i + 1] += n[13][i] / 10; n[13][i] = n[13][i] % 10;}
n[mi][k] = n[mi][k] % 10; n[12][k] = n[12][k] % 10; n[13][k] = n[13][k] % 10;//进位
p = false;
for (int i = 1; i <= ki; ++i)
if (n[mi][i] != n[1][i]) {
p = true;
break;
}//检验循环
++mi;
} while (p && (mi <= 11));//此时mi-2即为循环长度
for (int i = 1; i <= anslen; ++i) ans[i] *= mi - 2;
for (int i = 1; i <= anslen; ++i) { ans[i + 1] += ans[i] / 10; ans[i] = ans[i] % 10; }
if (ans[anslen + 1]) ++anslen; //ans *= mi - 2;
if ((mi == 12) && p) {
cout << -1 << endl;
return 0;
}
if (ki == k) {
for (int i = anslen; i >= 1; --i) cout << ans[i]; //输出ans
cout << endl;
return 0;
}
for (int i = 1; i <= k; ++i) n[0][i] = n[13][i]; //保存低位循环节
for (int i = 2; i <= mi - 1; ++i) for (int j = 1; j <= k; ++j) n[i][j] = 0; //清零
}
}