答案输出有解,我输出了 No Solution
。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int>vis;
void exgcd(int a,int b,ll &x,ll &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x); y-=(a/b)*x;
}
inline int qkpow(int a,int b,int p){
int res=1;
while(b){
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p; b>>=1;
}
return res;
}
int sol(int p,int b,int n){
if(n==1 or p==1){
return 0;
}
int m=ceil(sqrt(p)),tmp;
vis.clear();
for(int v=1;v<=m;v++){
vis[1ll*n*qkpow(b,v,p)%p]=v;
}
for(int u=1;u<=m;u++){
tmp=qkpow(b,u*m,p);
if(vis.count(tmp)){
return (u*m-vis[tmp]);
}
}
return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int a,p,b;
while(cin>>a>>p>>b){
if(!a) return 0;
a%=p,b%=p;
int tmp,val=1,tag=1,cnt=0,res=-1;
if(b==1 or p==1){
cout<<0<<"\n";
return 0;
}
while((tmp=__gcd(a,p))>1){
if(b%tmp){tag=0;break;}
b/=tmp,p/=tmp,cnt++;
val=1ll*val*(a/tmp)%p;
if(val==b){res=cnt;break;}
}
if(res>=0){
cout<<res<<"\n";
continue;
}
if(!tag){
cout<<"No Solution\n";
continue;
}
ll inv,num;
exgcd(val,p,inv,num);
b=1ll*b*inv%p;
tmp=sol(p,a,b);
if(tmp>=0) cout<<(tmp+cnt)<<"\n";
else cout<<"No Solution\n";
}
return 0;
}