思路
- 首先以下计算都是固定位数的
- 循环节也就是找到一个数跟自身相等,即 n*n^k==n 的话循环节就是k(位数一样,进位的舍去)
- 若我们找到最后一位的循环节为m,那么最后两位的循环节要找到abab^k==ab ,但是此时我们已经知道最后一位,也就是b每m次幂就是自身,那么我们可以确定每次k只要取m得整数倍即可,因为找到与自身相等的数的前提是最后一位相等,我们每次把k取m得整数倍就可以保证b是不变的,我们只要找到第一位相等的时候的情况,此时k=tm,t的取值情况最多有10种
- 为什么只有10种呢?因为最后一位是不变的,我们只需要看第一位的值,第一位循环节最多只有10(因为一位数字再怎么循环最大也只有10个)
- 另外数据范围特别的大,我们要用高精度乘法
- 每次比较是否和n相等时只需要比较第一位,因为我们已经保证后面的相等了
- 高精度乘法复杂度是O(k^2) ,需要循环k次,每次枚举十次,故总的时间复杂度是O(10k^3)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int ans[N],tem[N];
int per[N];//用来比较的
int npower[N];//类成用的
int power[N];//乘这个
int num[N];
int c[N];
string s;
int k;
void mul(int a[],int b[],int res[]){
memset(c,0,sizeof c);
for(int i=0;i<k;++i){
for(int j=0;j<k;++j){
if(i+j<k)c[i+j]+=a[i]*b[j];
}
}
int t=0;
for(int i=0;i<k;++i){
t+=c[i];
res[i]=t%10;
t/=10;
}
}
int main()
{
cin>>s;
cin>>k;
ans[0]=1;//答案
for(int i=0,j=s.size()-1;i<s.size();i++,j--)num[i]=s[j]-'0';
memcpy(npower,num,sizeof num);
for(int i=1;i<=k;++i){
memcpy(power,npower,sizeof npower);
memset(npower,0,sizeof npower);
npower[0]=1;
bool flag = false;
for(int j=1;j<=10;++j){
memset(tem,0,sizeof tem);
tem[0]=j;
mul(ans,tem,tem);
mul(npower,power,npower);
mul(num,npower,per);
if(per[i-1]==num[i-1]){
memcpy(ans,tem,sizeof tem);
flag=true;
break;
}
}
if(!flag){
cout<<-1<<endl;
return 0;
}
}
for(int i=k;i>=0;i--){
if(ans[i]){
for(int j=i;j>=0;j--){
cout<<ans[j];
}
break;
}
}
return 0;
}
厉害,不过这题能在考场上用这种方法想出来感觉太难了