BSGS

我们要求ax≡b(mod p)" role="presentation" style="position: relative;">ax≡b(mod p)$a^x\equiv b(modp)$中x的值，其中p为质数，或者a和p互质。
x可以写成：x=i∗k+j" role="presentation" style="position: relative;">x=i∗k+j$x=i\ast k+j$，其中k为常数。
那么ai∗k+j≡b" role="presentation" style="position: relative;">ai∗k+j≡b$a^{i\ast k+j}\equiv b$
ai∗k≡a−j∗b(mod p)" role="presentation" style="position: relative;">ai∗k≡a−j∗b(mod p)$a^{i\ast k}\equiv a^{-j}\ast b(modp)$
那么我们可以预处理每一个j的a−j∗b" role="presentation" style="position: relative;">a−j∗b$a^{-j}\ast b$，存进set或者map里，然后枚举i，看看map里存不存在ai∗k" role="presentation" style="position: relative;">ai∗k$a^{i\ast k}$。当k=φ(p)" role="presentation" style="position: relative;">k=φ(p)−−−−√$k=\sqrt{\phi (p)}$的时候复杂度最优。
当p和a不互质的时候，可以先把他们的gcd除干净（两边同时除gcd(a,p)之后可能gcd(a,p/d)!=0）

二次剩余

我们要求x2≡a(mod p)" role="presentation" style="position: relative;">x2≡a(mod p)$x^2\equiv a(modp)$中x的值，其中a<p" role="presentation" style="position: relative;">a<p$a<p$，x1−x2" role="presentation" style="position: relative;">x1−x2$x1-x2$显然不能是p的倍数，那么x1+x2=p，这样，我们发现每个x的平方会和另一个x的平方同余，而且他们的和为p，由于只有p-1个x，那么x2" role="presentation" style="position: relative;">x2$x^2$的值就只有(p-1)/2个。
定理2：若a(p−1)/2≡−1" role="presentation" style="position: relative;">a(p−1)/2≡−1$a^{(p-1)/2}\equiv -1$，那么x不存在，若=1，那么x必定存在且有两个，记为x1,x2，其中x1+x2=p。
证明：若=-1，那么由原方程可以推出xp−1≡−1" role="presentation" style="position: relative;">xp−1≡−1$x^{p-1}\equiv -1$，又有费马小定理xp−1≡1" role="presentation" style="position: relative;">xp−1≡1$x^{p-1}\equiv 1$，矛盾，所以x不存在。后者就是定理一的内容。
定义一个数的勒让德符号(ap)" role="presentation" style="position: relative;">(ap)$(\frac{a}{p})$他的取值有三个，1，-1，0，1代表a是p下的二次剩余，-1代表不是，0仅当a%p=0。那么易得(ap)=a(p−1)/2" role="presentation" style="position: relative;">(ap)=a(p−1)/2$(\frac{a}{p})=a^{(p-1)/2}$。 好了，现在我们来求x：
如果a不是二次剩余，返回无解。
如果是，那么有一个可行的做法如下：
首先找到一个c，使得c2−a" role="presentation" style="position: relative;">c2−a$c^2-a$的勒让德符号为-1，也即无法开根。
定义同余复数域，一个复数v=(a+bi)" role="presentation" style="position: relative;">v=(a+bi)$v=(a+bi)$，其中i=c2−a" role="presentation" style="position: relative;">i=c2−a−−−−−√$i=\sqrt{c^2-a}$，乘法等运算和通常意义上的复数一样。
有一个很强的结论：x=(a+i)(p+1)/2" role="presentation" style="position: relative;">x=(a+i)(p+1)/2$x=(a+i{)}^{(p+1)/2}$
很简单粗暴，可以证明右边做完幂运算之后虚部为0。 我们来感受一下他
x2=(a+i)p+1" role="presentation" style="position: relative;">x2=(a+i)p+1$x^2=(a+i{)}^{p+1}$
=(a+i)(a+i)p" role="presentation" style="position: relative;">=(a+i)(a+i)p$=(a+i)(a+i{)}^p$
=(a+i)∑j=0..pCpjaj ip−j" role="presentation" style="position: relative;">