题解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
string s;
int m, k; int i, j; int a[205], aans[205], n[205], ans[205], last[205], now[205], t[205];
int single_j[12] = { 1,1,4,4,2,1,1,4,4,2 };//单循环结
void init() {
memset(a, 0, sizeof a); memset(last, 0, sizeof last);
memset(aans, 0, sizeof aans); memset(now, 0, sizeof now);
memset(ans, 0, sizeof ans); memset(n, 0, sizeof n); memset(t, 0, sizeof t);
//for (int i = 1;; i++) { if (m == 0) break; n[i] = m % 10; m /= 10; }//将m存入数组n，以便于高精度
}
void multiplyh(int x[], int y[], int z[]) {//高精度高乘
int up = 0;
for (int ii = 1; ii <= k; ii++) {
for (j = 1; j <= k; j++)
{
z[ii + j - 1] += (x[j] * y[ii] + up) % 10;
up = (x[j] * y[ii] + up) / 10;
}
up = 0;
}
for (int ii = 1; ii <= k; ii++) {//进位
z[ii + 1] += z[ii] / 10;
z[ii] %= 10;
}
}
void multiplyl(int x[], int yy, int z[]) {//高精度低乘
int up = 0;
for (int ii = 1; ii <= k; ii++) {
z[ii] = (x[ii] * yy + up) % 10;
up = (x[ii] * yy + up) / 10;
}
}
int main()
{
//scanf("%d%d", &m, &k);
init();
cin >> s;
cin >> k;
int temp = 0, len = s.size();
for (i = len - 1; i >= len - k; i--)
n[temp] = s[i] - '0';
int tmp = 0;
for (int i = 1; i <= k; i) ans[i] = n[i];
for (int i = 1; i < single_j[n[1]]; i++) {
memset(aans, 0, sizeof aans);
multiplyh(ans, n, aans);
for (int j = 1; j <= k; j++) { ans[j] = aans[j]; }//更新为第一次出现末尾循环节的状态
}
t[1] = single_j[n[1]];//最低位的循环结
for (int i = 1; i <= k; i++) now[i] = ans[i];
int pos = 2;//当前倒数位数
while (pos <= k) {
for (int j = 1; j <= k; j++) {
ans[j] = n[j];
last[j] = now[j];
}
tmp = 0;
while (tmp < 11) {
tmp++;
memset(aans, 0, sizeof aans);
multiplyh(ans, now, aans);
for (j = 1; j <= k; j++) {
ans[j] = aans[j];
}
if (ans[pos] == n[pos]) break;//找到循环结
memset(aans, 0, sizeof(aans));
multiplyh(last, now, aans);//更新last
for (j = 1; j <= k; j++) last[j] = aans[j];
}
if (tmp >= 11) { cout << -1; return 0; }
for (int j = 1; j <= k; j++) now[j] = last[j];
memset(aans, 0, sizeof aans);
multiplyl(t, tmp, aans);//更新循环节数组
for (int i = 1; i <= 100; i++) t[i] = aans[i];
pos++;
}
int flag = 0;//不输出前导0
for (int i = 100; i >= 1; i--) {
if (t[i]) flag = 1;
if (flag) cout << t[i];
}
//cout << endl;
return 0;
}