Description has only two Sentences

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

Total Submission(s): 124 Accepted Submission(s): 55

Problem Description

_n = X*a

_n-1 + Y and Y mod (X-1) = 0.

Your task is to calculate the smallest positive integer k that a

_k mod a

₀ = 0.

Input

Each line will contain only three integers X, Y, a

₀ ( 1 < X < 2

³¹, 0 <= Y < 2

⁶³, 0 < a

₀ < 2

³¹).

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

Author

WhereIsHeroFrom

Source

HDOJ Monthly Contest – 2010.02.06

Recommend

wxl

/*题意：如题给出的递推公式，让你求出最小的k满足ak mod a0 ==0; 如果没有的话输出impossible初步思路：an=an-1*X+Y => an=Xn*a0+(1+X1+X2+.....+Xn-1)*Y  (里面有一个等比数列)                      => 然后两边同时膜a0 得到 an mod a0 = ( (Xn -1) * Y ) mod a0 / (X -1) = 0                      => 令 T=Y/(X-1) 得到0 =T (Xn - 1) mod a0 (T是任意整数 )                       => 将 mod a0 移到左边                      => 0 (mod a0) = T (Xn - 1)                           （这里的mod是提出来的）                      => 令p=__gcd(a0,T) 然后得到                      => 0 (mod a0/p) = T/p (Xn - 1) = 0 (mod a0') =T' (Xn - 1)                      => 此时a0' 和T' 互质了 那么得到                       => Xn-1=0 (mod a0') 如果(Xn -1 )mod a0' !=0那么就无解 即：                      => Xn mod a0' ==1  否则就是无解的情况                      然后就没有思路了.......#改进：由上一步能得出来 X^n=1(mod a0')                      => 欧拉定理，X^euler(a0')=1(mod a0');//其中X和a0'必须是互质的，不然没有解                      => 如果是互质的，那么然后就可以从a0'中的质因子枚举，然后快速幂就可以了#感悟：!!!质因子忘记排序了，错了两罚！！！！想吐，一天了，就想了这一个题。。。。*/#include
     
      #define ll long longusing namespace std;ll X,Y,A;ll T;/*******************分解质因子模板*********************/bool comp(ll a,ll b){    return a
      
       
        v;void find(ll n)//分解质因子{    v.clear();    ll m=(ll)sqrt(n+0.5);    for(ll i=1;i
        
         1) res=res/a*(a-1);     return res;}/**************************欧拉函数模板*****************************/int main(){    //freopen("in.txt","r",stdin);    while(scanf("%lld%lld%lld",&X,&Y,&A)!=EOF){        if(Y==0){            puts("1");            continue;        }        T=Y/(X-1);        ll p=__gcd(T,A);//最大公因子        //化简到最简单        T/=p;        A/=p;//a0'        //cout<
         
          <<" "<
          <