讨论 / 刚刚AC,C++高精度算法
七尾狮头兔 2020-08-11 23:37:50
点我顶贴 收藏 删除
不能暴力,逐个数位算吧。

高数位循环节是低数位循环节的倍数。

两个不同的高精度,一个算乘法,一个保存答案(答案那程度也必是高精度弄出来的)

为了方便我自己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; //清零

}

}

查看更多回复
提交回复