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 long
using 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=;i<m;i++)
if(n%i==){
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==) return ;
ll t=power(n,x/,mod);
t=t*t%mod;
if(x%==) t=t*n%mod;
return t;
}
/************快速幂模板****************/ /**************************欧拉函数模板*****************************/
//直接求解欧拉函数
ll euler(ll n){ //返回euler(n)
ll res=n,a=n;
for(int i=;i*i<=a;i++){
if(a%i==){
res=res/i*(i-);//先进行除法是为了防止中间数据的溢出
while(a%i==) a/=i;
}
}
if(a>) res=res/a*(a-);
return res;
}
/**************************欧拉函数模板*****************************/ int main(){
//freopen("in.txt","r",stdin);
while(scanf("%lld%lld%lld",&X,&Y,&A)!=EOF){
if(Y==){
puts("");
continue;
}
T=Y/(X-);
ll p=__gcd(T,A);//最大公因子
//化简到最简单
T/=p;
A/=p;//a0'
//cout<<T<<" "<<A<<endl;
if(__gcd(X,A)!=){//如果这两个数不是互质的，由欧拉定理的肯定是无解的
printf("Impossible!\n");
}else{
//X^euler(a0')=1(mod a0')
ll cur=euler(A);
find(cur);//分解质因子，打到p中
//cout<<v.size()<<endl;
for(int i=;i<v.size();i++){
//cout<<power(X,v[i],A)<<endl;
if(power(X,v[i],A)==){
printf("%lld\n",v[i]);
break;
}
}
}
}
return ;
}