题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3307
Description has only two Sentences
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1733 Accepted Submission(s):
525
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.
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).
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!".
is no such k, output "Impossible!".
Sample Input
2 0 9
Sample Output
1
an = X*an-1 + Y ，给你X,Y,a0，叫你求出最小的整数k(k>0)使得 ak% a0=0。根据公式我们可以求出an= a0*Xn-1+(x0+x1+x2+……+xn-1)Y。由等比数列前项和公式可得
an=a0*Xn-1+(xn-1)*Y/(x-1)。
所以只需令(xk-1)*Y/(x-1)%a0=0，求出k的值。
令Y'=Y/(x-1),d=gcd(Y/(x-1),a0)
Y'/=d,a0/=d;
此时Y'与a0互质
(xk-1)*Y/(x-1)%a0=0
等价于
(xk-1)%a0=0
xk%a0=1
而这就符合欧拉定理aφ(n)Ξ 1(mod n)
xφ(a0)Ξ 1(mod a0)
如果gcd(x,a0)!=1则k无解
否则k为phi(a0)除以满足条件的phi(a0)的因子
#include<iostream>
using namespace std;
#define ll long long
ll zys[][],cnt;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll phi(ll x)
{
ll ans=x;
for(ll i=;i*i<=x;i++)
{
if(x%i==)
{
ans=ans/i*(i-);
while(x%i==)x/=i;
}
}
if(x>)
ans=ans/x*(x-);
return ans;
}
void fj(ll ans)
{
for(ll i=;i*i<=ans;i++)
{
if(ans%i==)
{
zys[cnt][]=i;
zys[cnt][]=;
while(ans%i==)
{
ans/=i;
zys[cnt][]++;
}
cnt++;
}
}
if(ans>)
{
zys[cnt][]=ans;
zys[cnt++][]=;
}
}
ll poww(ll a,ll b,ll mod)
{
ll ans=;
while(b)
{
if(b&)ans=ans*a%mod;
a=a*a%mod;
b>>=;
}
return ans;
}
int main()
{
ll x,y,a,c,d;
while(cin>>x>>y>>a)
{
if(x==)
{
if(gcd(y,a)==)cout<<a<<endl;
else cout<<a/gcd(y,a);
continue;
}
c=y/(x-);
if(c%a==)
{
cout<<<<endl;
continue;
}
d=gcd(c,a);
if(gcd(x,a/d)!=)cout<<"Impossible!"<<endl;
else
{
a/=d;
ll ans=phi(a);
cnt=;
fj(ans);
for(int i=;i<cnt;i++)
{
for(int j=;j<=zys[i][];j++)
{
if(poww(x,ans/zys[i][],a)==)ans/=zys[i][];
}
}
cout<<ans<<endl;
}
}
return ;
}