BSGS
给定\(a,b,p\)，求\(x\)使得\(a^x\equiv b \pmod p\)，或者说明不存在\(x\)
只能求\(\gcd(a,p)=1\)的情况
有一个结论：如果有解则必然存在\(x\in\left\{0\ldots p-1\right\}\)的解
设\(q=\lceil\sqrt p\rceil,x=cq-d\)
\[a^{cq-d}\equiv b\pmod p\]
\[a^{cq}\equiv b\times a^d\pmod p\]
先枚举\(d\in\left\{1\ldots q\right\}\)，把\(b\times a^d \pmod p\)塞进哈希表里
再枚举\(c\in\left\{1\ldots q\right\}\)，查询\(a^{cq}\)是否在哈希表内
最后\(cq-d\)就是答案
扩展BSGS
能求\(\gcd(a,p)\neq1\)的情况。
设\(s=\gcd(a,p)\)
若\(s\nmid b\)则无解
设\(a'=\frac{a}{s},b'=\frac{b}{s},p'=\frac{p}{s}\)
\[(a's)^x\equiv b's\pmod {p's}\]
\[a'a^{x-1}\equiv b' \pmod {p'}\]
这样每次\(p\)都会除以一个大于\(2\)的数，这个过程一定会停止（\(O(\log p)\)次）
最后会得到
\[da^{x-k}\equiv b\pmod p\]
把计算出来的\(x\)加上\(k\)输出就可以了。
但是可能存在小于\(k\)的答案
直接枚举\(0\)~\(k\)，判断是否合法。
一些其他的东西
sdchr大爷说可以直接按照普通BSGS的方法做，然后把我的随机数据过掉了，但被我hack了。
表面上看当\(\gcd(a,p)\neq1\)时BSGS也可以做，但是，
\[a^{cq-d}\equiv b\pmod p\Rightarrow a^{cq}\equiv ba^d\pmod p \]
\[a^{cq-d}\equiv b\pmod p\nLeftarrow a^{cq}\equiv ba^d\pmod p\]
1式能推出2式，但2式不能推出1式（要两边同时除以\(a\)的逆元）
所以这是不对的