首页 > 代码库 > HDU3307 Description has only two Sentences 欧拉函数 欧拉定理
HDU3307 Description has only two Sentences 欧拉函数 欧拉定理
Description has only two SentencesTime 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 欧拉函数 欧拉定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。