学原根发现拔山盖世算法忘光了，干脆一块儿写了吧。
\(BSGS\) 算法
\(BSGS\) 算法，又名拔山盖世算法、北上广深算法。他解决的问题如下：
求解最小的可行的 \(k\)，满足 \(a^k\equiv b(\bmod p)\)，其中保证 \(\gcd(a,p)=1\)。
容易想到暴力枚举，时间复杂度 \(O(p)\)，但是巨劣，考虑优化。
优化算法哪家强，出门右转找分块。我们尝试使用分块的思路优化。
开始推导公式：
\[a^k\equiv b(\bmod p) \]\[a^{nA-m}\equiv b(\bmod p) \]\[a^{nA}\equiv ba^m(\bmod p) \]那我们考虑对 \(m\in[0,A)\) 进行暴力计算，用 \(map\) 或 \(unordered\_map\) 存储，然后暴力枚举 \(n\)，寻找此时有没有值与他同余。
时间复杂度 \(O(A+\frac pA)\)，当 \(A=\sqrt p\) 时，时间复杂度最小，为 \(O(\sqrt p)\)。
int bsgs(int a,int b,int p){
int kl=ceil(sqrt(p)),tmp=qpow(a,kl);
for(int i=0;i<kl;i++) mp[b]=i,b=b*a%p;
for(int i=1,c=1;i<=kl;i++)
if(mp[c=c*tmp%p]) return i*kl-mp[c];
return 0;
}
原根
定义：\(m\in \mathbb{N^*},g\in \mathbb{Z}\)，若 \(\gcd(m,g)=1\) 且 \(\delta_m(g)=\varphi(m)\)，我们称 \(g\) 为 \(m\) 的原根。
判定定理：\(g\) 为 \(m\) 原根，当且仅当 \(\forall p\in\{x|(x|\varphi(m),x\in prime)\},g^{\frac{\varphi(m)}{p}}\not\equiv1(\bmod m)\)。
对于一个有原根的数 \(m\)，它的原根个数为 \(\varphi(\varphi(m))\)。
若\(g\) 为 \(m\) 原根，则有 \(\forall i,j\in[0,p),g^i\not\equiv g^j(\bmod m)\)。
一个数 \(m\) 有原根，当且仅当 \(m\in\{2,4,p^a,2p^a\}\)。
标签：原根,int,bmod,笔记,算法,varphi,BSGS,equiv From： https://www.cnblogs.com/chang-an-22-lyh/p/18676603/yuan_gen_and_bsgs-zj对于一个有原根的数，它的最小正原根大小为 \(O(p^{0.25+\epsilon})\)，其中 \(\epsilon>0\)。
注：王元先生似乎的确没有证明非质数的情况，但是其他人证了，所以可以直接用，没有问题。