首页 > 代码库 > 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(欧拉定理 +快速幂+分解质因数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。