思路：BSGS模板题，并且该题由于b与p互质，因此我们可以直接使用朴素的BSGS算法求解，算法讲解链接：BSGS简易讲解。
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define maxn 100050
#define SQ 1005
#define ll long long
ll p,n,b;
ll q(ll x,ll y,ll m){
ll res=1;
x=x%m;
while(y){
if(y&1)
res=res*x%m;
x=x*x%m;
y/=2;
}
return res;
}
ll BSGS(ll a,ll b,ll m){
map<ll,ll> hs;
ll cur=b*a%m,t=sqrt(m)+1;
for(int B=1;B<=t;++B){
hs[cur]=B;
cur=cur*a%m;
}
ll at=q(a,t,m),now=at;
for(int A=1;A<=t;A++){
if(hs[now])
return A*t-hs[now];
now=now*at%m;
}
return -1;
}
int main(void){
scanf("%lld%lld%lld",&p,&b,&n);
ll ans=BSGS(b,n,p);
if(ans==-1)
printf("no solution\n");
else
printf("%lld\n",ans);
return 0;
}
本文地址：https://blog.csdn.net/haut_ykc/article/details/109274720