VII.exBSGS（扩展大步小步算法）
同理，exBSGS适用于 \(a^x\equiv b\pmod p\) 的情形。只不过，这里不再要求 \(a\perp p\)（这里 \(\perp\) 符号表示互质）。
若 \(\gcd(a,p)\neq1\)，则记其为 \(d_1\)，显然 \(a\) 的无论什么正次幂都是 \(d_1\) 的倍数，故若 \(b\nmid d_1\)，显然方程无解；否则，显然可以所有东西同除 \(d_1\)，得到 \(\dfrac{a}{d_1}\times a^{x-1}\equiv\dfrac b{d_1}\pmod{\dfrac{p}{d_1}}\)。
若此时 \(a\) 与 \(\dfrac{p}{d_1}\) 仍不互质，就继续下去，直到出现了一组 \(d_1,d_2,\dots,d_k\)，除完后它们变得互质，就可以做了。
记 \(D=\prod\limits_{i=1}^kd_i\)。则式子就是 \(\dfrac{a^k}{D}\times a^{x-k}\equiv\dfrac{b}{D}\pmod{\dfrac{p}{D}}\)。
特判掉 \(x=0\sim k\) 时是否相等，然后就直接按照常规BSGS处理即可。
时间复杂度仍为 \(\sqrt{n}\)，如果手写哈希表或者 unordered_map。
需要注意的是，因为并不能确定 \(\dfrac{a^k}{D}\) 一定与 \(\dfrac{p}{D}\) 互质，所以不能把它除过去，就老老实实让它在左边待着就行了。
VII.I.【模板】扩展BSGS
虽然是模板，但是还是有一堆要特判的东西。
- \(p=1\) 或 \(b\equiv1\pmod p\)。
此时答案只能为 \(0\)。
- \(a\equiv0\pmod p\) 。
此时，若 \(b\equiv0\pmod p\)，答案就是 \(1\)；若 \(b\equiv1\pmod p\)，答案是 \(0\)（但是这个我们之前已经特判过了）；否则判无解。
同时，还有几个细节：在特判 \(x=0\sim k\) 时要多跑几位，反正我是跑到 \(k+2\)；BSGS中的”大步“部分也要多跑几位。
并且，如果 \(b\nmid d_1\) 时，不要急着判无解，不管三七二十一先测一发 \(x=0\sim k\) 再说，不然 39 45 39 这组样例会把你卡死。
代码：
#include<bits/stdc++.h>
using namespace std;
int a,p,b;
unordered_map<int,int>mp;
int main(){
while(true){
scanf("%d%d%d",&a,&p,&b);
if(!a&&!p&&!b)break;
if(p==1||b==1){puts("0");continue;}
a%=p,b%=p;
if(!a){
if(!b)puts("1");else puts("No Solution");
continue;
}
// printf("%d %d %d\n",a,b,p);
int A=1,B=b,P=p,k=0;
while(__gcd(a,P)!=1){
int d=__gcd(a,P);
// printf("%d\n",d);
k++,A=(1ll*A*a/d)%p;
if(B%d){B=-1;break;}
B/=d,P/=d;
}
bool fd=false;
for(int i=0,j=1;i<=k+2;i++,j=1ll*j*a%p)if(j==b){printf("%d\n",i),fd=true;break;}
if(fd)continue;
if(B==-1){puts("No Solution");continue;}
A%=P,a%=P,B%=P;
// printf("%d %d %d %d\n",A,a,B,P);
// puts("IN");
mp.clear();
int K=sqrt(P);
int S=1;
for(int i=0;i<K;i++)mp[1ll*S*B%P]=i,S=1ll*S*a%P;
for(int i=1,j=1ll*S*A%P;i<=K+2;i++,j=1ll*j*S%P)if(mp.find(j)!=mp.end()){printf("%d\n",i*K-mp[j]+k),fd=true;break;}
if(!fd)puts("No Solution");
}
return 0;
}