首页 > 代码库 > hdu 3307 Description has only two Sentences (欧拉函数+快速幂)
hdu 3307 Description has only two Sentences (欧拉函数+快速幂)
Description has only two Sentences
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 852 Accepted Submission(s): 259
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
因为考试放下了挺久，后来发现不做题好空虚寂寞...于是决定在做一段时间再说。
1 //31MS 236K 1482 B G++ 2 /* 3 4 又是不太懂的数学题，求ak，令ak%a0==0 5 6 欧拉函数+快速幂： 7 欧拉函数相信都知道了。 8 首先这题推出来的公式为： 9 ak=a0+y/(x-1)*(x^k-1);10 11 明显a0是可以忽略的，其实就是要令 12 y/(x-1)*(x^k-1) % a0 == 0;13 可令 m=a0/(gcd(y/(x-1),a0))，然后就求k使得14 (x^k-1)%m==0 即可15 即 x^k==1(mod m)16 17 又欧拉定理有：18 x^euler(m)==1(mod m) (x与m互质，不互质即无解)19 20 由抽屉原理可知 x^k 的余数必在 euler(m) 的某个循环节循环。21 故求出最小的因子k使得 x^k%m==1，即为答案 22 23 */24 #include<stdio.h>25 #include<stdlib.h>26 #include<math.h>27 __int64 e[1005],id;28 int cmp(const void*a,const void*b)29 {30 return *(int*)a-*(int*)b;31 }32 __int64 euler(__int64 n)33 {34 __int64 m=(__int64)sqrt(n+0.5);35 __int64 ret=1;36 for(__int64 i=2;i<=m;i++){37 if(n%i==0){38 ret*=i-1;n/=i; 39 }40 while(n%i==0){41 ret*=i;n/=i;42 }43 }44 if(n>1) ret*=n-1;45 return ret;46 }47 __int64 Gcd(__int64 a,__int64 b)48 {49 return b==0?a:Gcd(b,a%b);50 }51 void find(__int64 n)52 {53 __int64 m=(__int64)sqrt(n+0.5);54 id=0;55 for(__int64 i=1;i<m;i++)56 if(n%i==0){57 e[id++]=i;58 e[id++]=n/i;59 }60 if(m*m==n) e[id++]=m;61 }62 __int64 Pow(__int64 a,__int64 b,__int64 mod)63 {64 __int64 t=1;65 while(b){66 if(b&1) t=(t*a)%mod;67 a=(a*a)%mod;68 b/=2;69 } 70 return t;71 } 72 int main(void)73 {74 __int64 x,y,a;75 while(scanf("%I64d%I64d%I64d",&x,&y,&a)!=EOF)76 {77 if(y==0){78 puts("1");79 continue;80 } 81 __int64 m=a/(Gcd(y/(x-1),a));82 if(Gcd(m,x)!=1){83 puts("Impossible!");84 continue;85 }86 __int64 p=euler(m);87 find(p);88 qsort(e,id,sizeof(e[0]),cmp);89 for(int i=0;i<id;i++){90 if(Pow(x,e[i],m)==1){91 printf("%I64d\n",e[i]);92 break;93 }94 }95 }96 return 0; 97 }