求解 \(a^x\equiv b(\mod p)\).
大步小步算法，BSGS（baby-step giant-step），要求 \(gcd(a,p)=1\)，可在 \(O(\sqrt p)\) 时间复杂度内求解。
在 \(p<=10^{16}\) 时没有大问题。
方程的解满足 \(0<=x<p\).
令 \(t=\left \lceil \sqrt p \right \rceil,0<=j<t,x=i*t-j\)，则 \(a^{i*t-j}\equiv b(\mod p)\).
两边同时乘上 \(a^j\) 可得，\(a^{i*t}\equiv ba^j(\mod p)\).
对于所有的 \(j\in [0,t-1]\)，将 \(ba^j\) 插入 \(hash/map\) 中。
枚举所有的 \(i\in[0,t]\)，查找表中是否存在 \(a^{i*t}\)，若存在则可以得到对应的 \(j\) 与 \(x=i*t-j\).
inline int BSGS(int a,int b,int p){
b%=p;
if(b==1)return 0;/*特判*/
mp.clear();
int t=sqrt(p)+1,re=b;/*初始b*a^0*/
for(int i=0;i<t;i++)mp[re]=i,(re*=a)%=p;/*依次插入b*a^i*/
a=po(a,t,p);/*初值a^t*/
re=1;
for(int i=0;i<=t;i++){
int j=mp.find(re)==mp.end()?-1:mp[re];
if(j>=0&&i*t-j>=0)return i*t-j;
(re*=a)%=p;/*更新a^(i*t)*/
}
return -1;
}