问题：求$a^xequiv b (mod p)$的最小正整数解。
这时候就要用到BSGS（拔山盖世）算法。直接进入正题：
设$x=im-n$，
则原式等于$a^{im-n}equiv b (mod p)$。
移项，得$a^{im}equiv a^nb(mod p)$。
我们把所有$a^nb$的状态存到一个map里，然后枚举$a^{im}$，如果相等则找到最小正整数解。
当$m=sqrt p$时，算法效率最高。则$[1,m]$枚举$n$,$[1,m]$枚举$i$。
以上说的情况是$a$与$p$互质的情况。那么不互质该怎么做呢？
我们变换一下形式：$a*a^{x-1}equiv b (mod p)$。
移项，得$a*a^{x-1}+y*p=b$。
设$g=gcd(a,p)$，由裴蜀定理得，如果$b mod p≠0$，那么此同余方程无解。
左右两边同除$g$，得到$frac{a}{g}*a^{x-1}+y*frac{p}{g}=frac{b}{g}$，即$a^{x-1}equiv frac{b}{g}*(frac{a}{g})^{-1} (mod frac{p}{g})$
重复上述步骤，直到$gcd(a,p)=1$为止，然后就可以用普通的BSGS求啦。
注意要特判一下，如果$b=1$或$p=1$或者某一时刻$(frac{a}{g})^x=b'$，那么直接返回$0$即可。
注意各种情况下的模数！！！被这个坑了好久QAQ。
代码：
#include<bits/stdc++.h> #define int long long using namespace std; map<int,int> vis; int a,p,b; inline int gcd(int a,int b) { if(!b) return a; return gcd(b,a%b); } inline void exgcd(int a,int b,int &x,int &y) { if (!b) x=1,y=0; else{ exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; } } inline int inv(int a,int b) { int x,y; exgcd(a,b,x,y); return (x%b+b)%b; } inline int qcal(int a,int b,int p) { int res=1; while(b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; } return res; } inline int bsgs(int a,int b,int p) { vis.clear(); b%=p; int m=ceil(sqrt(p)); for (int i=1;i<=m;i++) b=b*a%p,vis[b]=i; b=1;int tmp=qcal(a,m,p); for (int i=1;i<=m;i++) { b=b*tmp%p; if (vis[b]) return (i*m-vis[b]+p)%p; } return -1; } inline int exbsgs(int a,int b,int p) { if (b==1||p==1) return 0; int g=gcd(a,p),k=0,na=1; while(g>1) { if (b%g!=0) return -1; b/=g;p/=g;na=na*(a/g)%p; k++; if (na==b) return k; g=gcd(a,p); } int f=bsgs(a,b*inv(na,p)%p,p); if (f==-1) return -1; return f+k; } signed main() { cin>>a>>p>>b; while(a||p||b) { a%=p;b%=p; int t=exbsgs(a,b,p); if (t==-1) puts("No Solution"); else printf("%lld ",t); cin>>a>>p>>b; } return 0; }