1101: 循环 高精度

解题思路:

规律:当后K为数字存在循环结的必要条件是，后K-1位数字存在循环结，并且K的最小循环结必定是K-1的最小循环结的整数倍。并且对于当前位数的处理不必要取模，既然已经用了数组高精度保存便可以只考虑当前位数。在比较时，显然后K-1位已经按照之前的循环结递推过来必定相同，我们只需要比较倒数第K位是否相等即可。

技巧:关于查找循环结上限的问题，当前位数出现可能是0,1.2.3,4,5.6,7,8.9，在10次之内必定会出现与第一次相同的情况，当前次数*K-1的循环结即可得到K的循环结。如果10之内未能出现，那肯定就不存在了。

注意事项: 循环节的长度可能会超出整数范围， 利用高精度乘法计算循环节长度

参考代码:

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int a[N], b[N], c[N],res[N]= {1};
int k,cnt = 1;
string s;
void mult(){
	for(int i = 0 ; i < k; i ++)
		for(int j = 0; j < k; j ++){
			c[i + j] += a[i] * b[j];
			c[i + j + 1] += c[i + j] / 10;
			c[i + j] %= 10;
	}
} 
void calc(int m,int size){
	int r = 0;
	for(int i = 0; i <= size; i ++){
		r += res[i] * m;
		res[i] = r % 10;
		r /= 10; 
	}
}
int main()
{
	cin >> s >> k;
	int idx = 0, n = s.size() - 1;
	while(n >= 0)	a[idx++] = s[n--] - '0';
	
	for(int i = 0; i < k; i ++){
		int j = 1;
		memcpy(b,a,sizeof a);
		for(; j <= 10; j ++ ){
			memset(c,0,sizeof c);
			mult(); 
			if(c[i] == b[i]) break;
			memcpy(a,c,sizeof c);
		}
		if(j > 10) {
			cout << -1;
			return 0;
		}
		else calc(j,cnt ++);
	}
	while(res[cnt] == 0) cnt --;
	for(int i = cnt; i >= 0; i --)
		cout << res[i]; 

	return 0;
}