bsgs问题。因为p可能不为质数,所以我们将原先解题的式子变形
每次除以p与a的最大公约数,直到最大公约数为1或b不能整除为止
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#define LL long long
using namespace std;
LL a,b,m,p,now,ans;
bool flag;
map<LL,int> mp;
inline LL fast_pow(LL a,LL b){
LL ret=1;
LL aa=a;
for(;b;b>>=1){
if(b&1) ret=ret*aa%p;
aa=aa*aa%p;
}
return ret;
}
int main(){
while(~scanf("%lld%lld%lld",&a,&p,&b)){
if(a==0 && b==0 && p==0) break;
if(a%p==0){
puts("No Solution");
continue;
}
if(b==1) {
puts("0");
continue;
}
flag=false;
a%=p;b%=p;
LL t=1,cnt=0;
for(register int i=__gcd(a,p);i!=1;i=__gcd(a,p)){
if(b%i){
puts("No Solution");
flag=1;
break;
}
p/=i;t=t*a/i%p;b/=i;cnt++;
if(b==t) {printf("%lld
",cnt);flag=1;break;}
}
if(flag) continue;
mp.clear();
now=b;
mp[now]=0;
m=ceil(sqrt(p));
for(register int i=1;i<=m;i++){
now=now*a%p;
mp[now]=i;
}
now=t;
LL k=fast_pow(a,m);
for(register int i=1;i<=m;i++){
now=now*k%p;
if(mp[now]){
flag=true;
ans=i*m-mp[now]+cnt;
printf("%lld
",ans);
break;
}
}
if(!flag) puts("No Solution");
}
return 0;
}