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
     
      25 #include
      
       26 #include
       
        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