HDU 3370 Description has only two Sentences （欧拉函数+欧拉定理）

欧拉定理表明，若n,a为正整数，且n,a互质，则:  

费马小定理:

a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)

证明这个定理非常简单，由于p是质数，所以有φ(p) = p-1，代入欧拉定理即可证明。推论：对于任意正整数a，有a^p ≡ a (mod p)，因为a能被p整除时结论显然成立。

Description has only two Sentences

a _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 ³¹).OutputFor each case, output the answer in one line, if there is no such k, output "Impossible!".

Sample Input

2 0 9

Sample Output

1
题意： 给出公式及x，y，a0的值（y%（x-1）=0），求使ak%a0=0的k的最小值。
思路：在纸上推一下可以推出所求的k值是使(x^k-1)*(y/(x-1))=0（mod a0）。令B=（y/(x-1）），为了使用欧拉定理，必须把（y/(x-1））消去，所以求gcd(a0,B),且a0=a0/gcd。
所以，问题转化为求最小的k使x^k=1(mod a0),而欧拉定理要求x与a0互质。所以，首先判断gcd(x,a0)是否为1：若不为1，则无解；否则用欧拉定理求解。
（先求出a0的欧拉函数值，然后枚举k的取值，注意用i*i<=phi(a0),不然会超时。）

AC代码：
#include <iostream> 
#include <cstdio> 
#include <algorithm>
#include <cstring> 
#include <string> 
#define LL long long 
using namespace std; 
LL euler(LL n) 
{ 
LL res=n,a=n; 
for(int i=2;i*i<a;i++) 
if(a%i==0) 
{ res=res/i*(i-1); 
  while(a%i==0) a/=i; } 
  if(a>1) res=res/a*(a-1); 
  return res; 
} 
LL gcd(LL a,LL b)
 { if(b==0) return a; else return gcd(b,a%b); } 
LL ppow(LL a,LL n,LL mod)
 { 
   LL ans=1; 
   while(n) { if(n%2==1) ans=(ans*a)%mod; a=(a*a)%mod; n/=2; }
   return ans%mod; 
  } 
  int main() 
  { 
    LL x,y,a0;
     while(scanf("%lld%lld%lld",&x,&y,&a0)!=EOF) { 
     LL c=y/(x-1); 
     LL g=gcd(c,a0); 
     a0/=g; 
     if(gcd(x,a0)!=1) {
     cout<<"Impossible!
";
     continue; 
     } 
     LL n=euler(a0); 
     LL m=n; 
     LL i;
     LL ans=n; 
     for(i=2;i*i<=m;i++) 
     { 
        if(m%i==0) 
        { 
         if(ppow(x,i,a0)==1) ans=min(ans,i);
         if(ppow(x,m/i,a0)==1) ans=min(ans,m/i); 
        } 
      }
      cout<<ans<<endl;
     } 


     return 0; 
  }