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 = 0. Input Each line will contain only three integers X, Y, a 0 ( 1 < X < 2 31, 0 <= Y < 2 63, 0 < a 0 < 2 31). 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
数论的定理见一个记一个。。。。 自己做的就不注释了。。。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; ll gcd(ll x,ll y) { return x%y?gcd(y,x%y):y; } 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 poww(ll a,ll b,int mod) { ll ans=1; while(b>0) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { ll x,a0; ll y; while(scanf("%lld%lld%lld",&x,&y,&a0)==3) { ll m=y/(x-1); ll d=gcd(m,a0); a0/=d; if(gcd(x,a0)!=1) cout<<"Impossible!"<<endl; else { ll ans=euler(a0); ll up=ans; for(int i=2;i*i<=up;i++) if(up%i==0) { if(poww(x,i,a0)==1)ans=min(ans,(ll)i); if(poww(x,up/i,a0)==1)ans=min(ans,up/i); } cout<<ans<<endl; } } return 0; }