算法分析:
直接枚举:用高精度乘法计算n的a次方,直到后k位出现循环,这样做有2个缺点:(1)时间复杂度过大,a的大小无法判断,可能会很超过MAXLONGINT,所以会超时 (2)无法判断不出现循环的情况
2.(1)可以发现,如果后k位循环,那么循环节一定是后k-1位循环的循环节的倍数
证明如下:设后k位循环节为a1,后k-1位循环的循环节是a2,且a1=p*a2+b(p,b是常数)
那么n^1的后k-1位=n^a2的后k-1位
n^1的后k位=n^a1的后k位->n^1的后k-1位=n^a1的后k-1位
所以n^a2的后k-1位等于n^a1的后k-1位...................................[1]
因为b不是循环节,所以n^(p*a2)的后k-1位不等于n^(p*a2+b)的后k-1位
n^(p*a2)的后k-1位等于n^a2的后k-1位
所以n^a2的后k-1位不等于n^a1的后k-1位,这与[1]矛盾,
所以我们可以求出后k-1位的循环节,再将后k-1位的循环节作为乘数求后k位的循环节(若n^a后k-1位与n的后k-1位相等,那么n^(a-1)为求后k位时的乘数),这样可以保证所枚举到的数一定是后k-1为循环节的倍数,而且可以大大减少枚举的数量
可以通过记录后k位循环节长度是后k-1的循环节的多少倍来求循环节,这样,枚举的数就不需要用高精度,最后结果相乘时用高精度
(2)整数的每一位有10种可能,如果某个长度枚举10次仍然没有循环的话,根据抽屉原理,因为这10个数中有1个没取到(就是该循环的一位)那么就一定出现了重复,也就是产生循环,但这个循环是以这9个数字中某个数开始的而不包括应该循环的那一位,那么意味着该循环的一位永远不会循环.那么这个时候就可以判断,这个数不会出现循环
这样做,上面直接枚举的2个问题都可以有效解决,
优化:
因为高精度计算中,计算后k位只需要保存后k位乘积的结果,而k范围较小,在计算是若判断大于k位则跳出,这样,节约了一定时间,同时也可以节约空间(因为结果只需存k位).
如果10次中已经出现循环的数,则可以退出
我的代码，比较肥。。。汗了
#include<iostream>
using namespace std;
typedef long long hugeint;
#define Base 10
#define MaxLen 500
int k;
struct BigNum 
{
int len;
int data[MaxLen];
BigNum() :len(0) {}
BigNum(const BigNum& s) :len(s.len){
memcpy(this->data,s.data,len*sizeof(*data));
}
BigNum(int s) :len(0){
for(;s>0;s=s/Base)
data[len++]=s%Base;
}
BigNum & operator = (const BigNum& s){
this->len=s.len;
memcpy(this->data,s.data,len*sizeof(*data));
return *this;
}
int& operator [](int index){ return data[index]; }
int operator [](int index) const { return data[index]; }
};
BigNum operator + (const BigNum & a, const BigNum & b){
BigNum c;
int i,carry=0;
c.len=a.len>b.len?a.len:b.len;
for(i=0;i<c.len||carry>0;++i){
if(i<a.len) carry+=a[i];
if(i<b.len) carry+=b[i];
c[i]=carry%Base;
carry/=Base;
}
c.len=i;
return c;
}
BigNum operator - (const BigNum & a, const BigNum & b){
BigNum c;
int lend=0, i;
c.len=a.len;
for(i=0; i<a.len; ++i){
c[i]=a[i]-lend;
if(i<b.len) c[i]-=b[i];
if(c[i]<0) lend=1,c[i]+=Base;
else lend=0;
}
while(c.len>0&&c[c.len-1]==0) --c.len;
return c;
}
BigNum operator * (const BigNum & a, const int b){
int i;
if(b==0) return 0;
BigNum c;
hugeint carry=0;
for(i=0;i<a.len;++i){
carry+=hugeint(a[i])*b;
c[i]=carry%Base;
carry/=Base;
}
for(;carry>0;++i){
c[i]=carry%Base;
carry/=Base;
}
c.len=i;
return c;
}
BigNum operator * (const BigNum & a, const BigNum & b){
int i,j;
if(b.len==0) return 0;
BigNum c;
hugeint carry;
for(i=0;i<a.len;++i){
carry=0;
for(j=0;j<b.len||carry>0;++j){
if(j<b.len) carry+=hugeint(a[i])*b[j];
if(i+j<c.len) carry+=c[i+j];
if((i+j)>=k) break;
if(i+j==c.len) c[c.len++]=carry%Base;
else c[i+j]=carry%Base;
carry/=Base;
}
}
return c;
}
BigNum operator / (const BigNum & a, const int b){
int i;
hugeint r=0;
BigNum c;
for(i=c.len-1;i>-1;--i){
r=r*Base+a[i];
c[i]=r/b;
r%=b;
}
c.len=a.len;
while(c.len>0&&c[c.len-1]==0) --c.len;
return c;
}
int compare(const BigNum & a, const BigNum & b){
int i;
if(a.len!=b.len) return a.len>b.len?1:-1;
for(i=a.len-1;i>-1&&a[i]==b[i];--i) ;
if(i==-1) return 0;
else return a[i]>b[i]?1:-1;
}
BigNum operator / (const BigNum & a, const BigNum & b){
int i;
BigNum c,carry=0;
int left,right,mid;
for(i=a.len-1;i>-1;--i){
carry=carry*Base+a[i];
left=0;
right=Base-1;
while(left<right){
mid=(left+right+1)/2;
if(compare(b*mid,carry)<=0)
left=mid;
else
right=mid-1;
}
c[i]=left;
carry=carry-b*left;
}
c.len=a.len;
while(c.len>0&&c[c.len-1]==0) --c.len;
return c;
}
BigNum operator % (const BigNum & a, const BigNum & b){
int i;
BigNum c,carry=0;
int left,mid,right;
for(i=a.len-1;i>-1;--i){
carry=carry*Base+a[i];
left=0;
right=Base-1;
while(left<right){
mid=(left+right+1)/2;
if(compare(b*mid,carry)<=0)
left=mid;
else
right=mid-1;
}
c[i]=left;
carry=carry-b*left;
}
c.len=a.len;
while(c.len>0&&c[c.len-1]==0) --c.len;
return carry;
}
istream & operator >> (istream & is, BigNum & s)
{
char ch;
for(s=0;is>>ch;){
s=s*10+(ch-'0');
if(cin.peek()<=' ')
break;
}
return is;
}
ostream & operator << (ostream & os, const BigNum & s)
{
int i,j;
os<<(s.len==0?0:s[s.len-1]);
for(i=s.len-2;i>-1;--i)
for(j=Base/10;j>0;j/=10)
os<<s[i]/j%10;
return os;
}
BigNum gcd(BigNum a, BigNum b){
if(b.len==0)
return a;
else
return gcd(b,a%b);
}
int main () {
BigNum n,num,step,mod,x;
int i,j,t,c[1001],flag;
while(cin>>n>>k){
if(compare(n,0)==0&&k==0)
break;
for(i=0;i<k;++i)
mod[i]=0;
t=-1;
mod[k]=1;
mod.len=k+1;
n=n%mod;
step=1;
x=n;
for(i=0;i<k;++i){
num=n;
step=x;
x=1;
flag=0;
for(j=0;j<10;++j){
num=num*step;
x=x*step;
if(num[i]==n[i]){
flag=1;
c[++t]=j+1;
break;
}
}
if(flag!=1)
break;
}
if(flag!=1){
printf("-1\n");
continue;
}
for(i=0,x=1;i<=t;++i)
x=x*c[i];
cout<<x<<endl;
}
return 0;
}