题面非常明显,需要用BSGS算法,即 必应搜索谷歌搜索 大步小步算法,其实就是板子题,开个map,写个快速幂就KO了
值得注意的是,如果B是P的倍数,那么N必须也是P的倍数,否则无解,需要特判一下
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
#define int long long
using namespace std;
int p,b,n;
map <int,int> mp;
int qpow(int a,int x,int p){
int s=1;
while (x){
if (x&1)s=s*a%p;
a=a*a%p;
x>>=1;
}
return s;
}
signed main(){
cin>>p>>b>>n;
if (b%p==0 && n%p!=0){//特判
cout<<"no solution"<<endl;
return 0;
}
int m=ceil(sqrt(p)),now=n%p;
for (int i=1;i<=m;i++){
now=now*b%p;
if (!mp[now])mp[now]=i;
}
now=qpow(b,m,p);
int tmp=now;
for (int i=1;i<=m;i++){
if (mp[now]){
cout<<((i*m-mp[now])%p+p)%p<<endl;
return 0;
}
now=now*tmp%p;
}
cout<<"no solution"<<endl;
return 0;
}