首页 > 代码库 > HDU3307 Description has only two Sentences 欧拉函数 欧拉定理

HDU3307 Description has only two Sentences 欧拉函数 欧拉定理

 

 


Description has only two Sentences

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)


Problem Description
an = X*an-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.
 

Input
Each line will contain only three integers X, Y, a0 ( 1 < X < 231, 0 <= Y < 263, 0 < a0 < 231).
 

Output
For each case, output the answer in one line, if there is no such k, output "Impossible!".
 

Sample Input
2 0 9
 

Sample Output
1
 

Author
WhereIsHeroFrom
 

Source
HDOJ Monthly Contest – 2010.02.06
 

Recommend
wxl   |   We have carefully selected several similar problems for you:  3308 3309 3306 3310 3314 

 

 


构造等比数列,先设p=y/(x-1);那么有(An+p)=x(An-1+p)  即 An+p=x^n(a0+p)

若An≡0(mod a0) 即 a0*x^n+p*(x^n - 1) ≡ 0 ≡ p*(x^n - 1)(mod a0)

同余方程两边同除gcds=gcd(p,a0),可得 p/gcds * (x^n - 1) ≡ 0 (mod a0/gcds)  *

∵ (p/gcds,a0/gcds) = 1

*式可化为 x^n-1≡0 (mod ap=a0/gcds) 即 x^n ≡ 1 (mod ap)

根据欧拉定理可知 n = phi(ap) ,下面同反证法证明所求的k满足  k|n,k<=n

假设求得最小的满足题意的k 且 k \ n (记\为不整除)   

那么一定存在t使得k*t恰大于n,那么k*t-n也一定满足题意,但kt-n<k与条件矛盾,即k|n,k<=n

 1 #include<set> 2 #include<cmath> 3 #include<queue> 4 #include<cstdio> 5 #include<cstdlib> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 using namespace std;10 typedef long long lld;11 #define For(i,n) for(int i=1;i<=n;i++)12 #define Rep(i,l,r) for(int i=l;i<=r;i++)13 lld gcd(lld a,lld b){14     if(!b) return a;15     else   return gcd(b,a%b);16 }17 18 lld Min(lld a,lld b){return (a<b)?(a):(b);}19 20 lld phi(lld n){21     lld ans=n;lld lim=sqrt(n);22     Rep(i,2,lim){23         if(n%i==0)  {24             ans=ans*(i-1)/i;25             while(n%i==0) n/=i;26         }27     }28     if(n>1) ans=ans*(n-1)/n;29     return ans;30 }31 32 lld x,y,a0,ap;33 34 lld qpow(lld a,lld b){35     lld ans=1;36     while(b){37         if(b&1) ans=(ans*a)%ap;38         a=a*a%ap;39         b>>=1;40     }41     return ans%ap;42 }43 44 int main(){45     while(~scanf("%I64d%I64d%I64d",&x,&y,&a0)){46         lld p=y/(x-1);47         lld gcds=gcd(a0,p);48         ap=a0/gcds;49         if(gcd(x,ap)!=1){50             puts("Impossible!");51             continue;52         }53         lld ans=phi(ap);lld Lim=ans;54         Rep(i,2,sqrt(Lim))55           if(Lim%i==0){56               if(qpow(x,i)==1)  ans=Min(ans,i);57               if(qpow(x,Lim/i)==1) ans=Min(ans,Lim/i);58           }59         printf("%I64d\n",ans);60     }61     return 0;62 }

 

HDU3307 Description has only two Sentences 欧拉函数 欧拉定理