首页 > 代码库 > Description has only two Sentences(欧拉定理 +快速幂+分解质因数)

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): 124 Accepted Submission(s): 55
 
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
 
/*题意:如题给出的递推公式,让你求出最小的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<bits/stdc++.h>#define ll long longusing namespace std;ll X,Y,A;ll T;/*******************分解质因子模板*********************/bool comp(ll a,ll b){    return a<b;}vector<ll>v;void find(ll n)//分解质因子{    v.clear();    ll m=(ll)sqrt(n+0.5);    for(ll i=1;i<m;i++)        if(n%i==0){            v.push_back(i);            v.push_back(n/i);        }    if(m*m==n) v.push_back(m);    sort(v.begin(),v.end(),comp);}/*******************分解质因子模板*********************//************快速幂模板****************/ll power(ll n,ll x,ll mod){    if(x==0) return 1;    ll t=power(n,x/2,mod);    t=t*t%mod;    if(x%2==1) t=t*n%mod;    return t;}/************快速幂模板****************//**************************欧拉函数模板*****************************///直接求解欧拉函数ll euler(ll n){ //返回euler(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;}/**************************欧拉函数模板*****************************/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<<T<<" "<<A<<endl;        if(__gcd(X,A)!=1){//如果这两个数不是互质的,由欧拉定理的肯定是无解的            printf("Impossible!\n");        }else{            //X^euler(a0‘)=1(mod a0‘)            ll cur=euler(A);            find(cur);//分解质因子,打到p中            //cout<<v.size()<<endl;            for(int i=0;i<v.size();i++){                //cout<<power(X,v[i],A)<<endl;                if(power(X,v[i],A)==1){                    printf("%lld\n",v[i]);                    break;                }            }        }    }    return 0;}

 

Description has only two Sentences(欧拉定理 +快速幂+分解质因数)