bsgs，北上广深，拔山盖世，蓝超巨星（blue super giant star）。大概是\(O(\sqrt n)\)求解模意义下离散对数的一个算法。经典的平衡复杂度思想。
离散对数，也就是长这样的一个东西：
\[a^x\equiv b\mod p \]其中\(p\)是个质数，给你\(a,b,p,\)求最小的正整数\(x\)。
首先我们根据费马小定理知道\(a^x\)是个循环的，而且一个循环节是\(p-1\)。当然不一定是最小循环节。当然，我们不能暴力搞。这时我们就用到了一个重要思想：平衡复杂度的思想。
具体的，我们随便设个\(t\)（先在这挂着，取值一会再说），然后开始导柿子：
\[a^x\equiv b \mod p \]设\(x=i\cdot t-j\)。
\[a^{i\cdot t-j}\equiv b \mod p \]\[a^{i\cdot t}\equiv b\cdot a^j \mod p \]对这个柿子，我们可以预处理每个\(a^j\)，然后枚举\(i\)来找。显然\(j<t\)。当\(t=\sqrt n\)时，复杂度最低，为\(O(\sqrt n)\)。
知道原理之后代码其实很好写。
unordered_map<int,int>mp;
int bsgs(int a,int b){
mp.clear();
int sq=sqrt(mod)+1;
int tmp=b;
for(int i=0;i<sq;i++){
mp[tmp]=i;//先预处理所有的j放到哈希表里
tmp=1ll*tmp*a%mod;
}
a=qpow(a,sq);
if(!a)return b==0?1:-1;//特判一下有无解
for(int i=1,val=1;i<=sq;i++){//枚举所有i
val=1ll*val*a%mod;
if(mp.find(val)!=mp.end())return i*sq-mp[val];//查找能不能找到对应的j
}
return -1;
}