[HDU 3307 Description has only two Sentences]数论、素论、取余的性质

【题目大意】

a_n = X*a_n-1 + Y      保证 y mod (x-1)=0

求最小的Ak mod a0=0

【算法分析】

先用等比数列求和公式得到通项。

最后推导出求x^k = 1 (mod a0)，然后再利用欧拉函数求解。

具体看这里吧http://hi.baidu.com/aekdycoin/blog/item/e5224da98d6c2fbaca130c67.html

后面的欧拉函数部分还不是很懂。。。

【CODE】

#include #include #include using namespace std;
__int64 x,y,a0;

__int64 phi(__int64 a){
    __int64 r=a;
    for (__int64 i=2;i<=a/i;i++)
    if(a%i==0){
        r-=r/i;
        while(a%i==0)
          a/=i;
    }
    return a<2?r:r-r/a;
}   

__int64 gcd(__int64 a,__int64 b){
    if (b==0) return a;
    return gcd(b,a%b);
}  

__int64 mod(__int64 a,__int64 b,__int64 c){
    __int64 r=1%c;
    while(b){
        if(b&1)r=r*a%c;
        a=a*a%c;
        b=b/2;
    }
    return r;
}   

void solve(){
    __int64 c=y/(x-1),g=gcd(c,a0);
    if (c%a0==0){
        printf("1n");
        return;
    }   
    a0/=g;
    if (gcd(a0,x)>1){
        printf("Impossible!n");
        return;
    }   
    __int64 times=phi(a0),ans=0x7FFFFFFF;
    for (__int64 i=1;i<=times/i;i++)
      if (times % i==0){
        if (mod(x,i,a0)==1) ans=min(ans,i);
        if (mod(x,times/i,a0)==1) ans=min(ans,times/i);
    }   
    if (ans==0x7FFFFFFF) printf("Impossible!n");
                    else printf("%I64dn",ans);
}   

int main(){
    while (scanf("%I64d%I64d%I64d",&x,&y,&a0)!=EOF){
        solve();
    }   
    return 0;
}