tctony

Focus on linux,emacs,c/c++,python,algorithm...

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  17 随笔 :: 0 文章 :: 7 评论 :: 0 Trackbacks

Description

乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天,他突然对数的正整数次幂产生了兴趣。众所周知,2的正整数次幂最后一位数总是不断的在重复2,4,8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑最小的循环长度)。类似的,其余的数字的正整数次幂最后一位数也有类似的循环现象:
循环 循环长度
2 2、4、8、6 4
3 3、9、7、1 4
4 4、6 2
5 5 1
6 6 1
7 7、9、3、1 4
8 8、4、2、6 4
9 9、1 2
这时乐乐的问题就出来了:是不是只有最后一位才有这样的循环呢?对于一个整数n的正整数次幂来说,它的后k位是否会发生循环?如果循环的话,循环长度是多少呢?注意: 1.如果n的某个正整数次幂的位数不足k,那么不足的高位看做是0。 2.如果循环长度是L,那么说明对于任意的正整数a,n的a次幂和a + L次幂的最后k位都相同。

Input

输入包含多组数据,每组数据占一行,包含两个整数n(1 <= n < 10100)和k(1 <= k <= 100),n和k之间用一个空格隔开,表示要求n的正整数次幂的最后k位的循环长度。输入以 0 0结束。

Output

输出包括一行,这一行只包含一个整数,表示循环长度。如果循环不存在,输出-1。

Sample Input

32 2
125 3
1232135 4
0 0


Sample Output

4
2
-1


 

算法分析:
直接枚举:用高精度乘法计算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==-1return 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;
}


posted on 2007-12-08 16:49 tctony 阅读(299) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理