炒冷饭
求逆元
exgcd(a,m,x,y); ans=(x%m+m)%m;，万能。qpow(a,m-2,m)，这个仅限于m是一个质数。inv[i]=(m-m/i)*inv[m%i]%m，线性求逆元。
中国剩余定理(CRT)
现在已知一个同余方程组:
满足(m_i)两两互质。
解法：
首先计算出下面的各个值：
那么最终的答案就是：
我不会证明
扩展中国剩余定理(EXCRT)
现在解决的是(m_i)可能不两两互质的情况。
符号约定：
(mathrm{inv}(a,m))表示(a)在模(m)下的逆元。
((a,b)=gcd(a,b))
考虑将两条方程进行合并。
现在有两条方程：
转化为不定方程的形式：
那么可以得到：
可以发现，这个方程有解的条件是((m_1, m_2)|(a_2-a_1))，方程两边同时除以((m_1, m_2)),然后化为同余式：
可以发现此时((frac{m_1}{(m_1, m_2)}, frac{m_2}{(m_1,m_2)})=1)，所以同余式两边同时乘上逆元：
接着将其再次转化为一个不定方程，然后带入(x)：
然后转化为同余式：
这样就合并成功了。
同余式的转化
在实际问题中，可能给出的同余式是类似下面这个样子的：
我们需要将其转化为(EX)CRT的形式的形式。
将其转化为不定方程的形式：
可以发现，这个方程有解的条件是((a,M)|b)。
首先使用exgcd求出方程(ax+My=(a,M))的特解，得到的一组解为(x',y')。
那么原方程的一组解为
那么原方程的通解就是
我们取x的通解表达式，将其转化为同余式：
新内容
基本概念
阶:当((a,p)=1)时，满足(a^xequiv 1~~~~(mathrm{mod}~~p))的最小(x)，计作(delta_p(a))。
原根:如果(delta_p(a)=varphi(p))，那么(a)就是模(p)下的原根。一个模数由原根，就必须先满足(p=2,4,p^n,2p^n)。
如果(p)是一个质数，那么可以用(a^x\%p)表示([1,p-1])中的所有数，其中(1leq xleq p-1)
二次剩余
形式化的，就是找到满足下面的同余式的(x):
通俗点来讲，就是将(a)在模(p)以一下进行开根。
如果(a)能够开根（上面的同余方程有解），那么我们就可以认为“(a)是模(p)意义下的二次剩余”，否则认为“(a)不是模(p)意义下的二次剩余”。
上面同余方程要么有两个解（可能相同），要么没有解。
如果(p=2)，那么显然的，x的取值只有0/1，而且很容易找到，所以我们只讨论(p)属于奇素数的情况。
引理1:对于一个模数(p)，是二次剩余的数共有(frac{p-1}{2})（不包括(0)）,非二次剩余的数也有(frac{p-1}{2})个，各占一半。
虽然我们很难在较短时间内准确知道是二次剩余的数的分布，但是没有关系。
引理2:对于一个数(a)和一个模数(p),可以得到：
接下来考虑算法（忽略各种特判）。
首先可以想到，第一步一定是判断一个数(a)是否是二次剩余。
如果是一个二次剩余，那么继续执行算法，找到(x)，否则直接返回一个表示不是二次剩余的结果。
接下来就是一系列神仙操作。
随机一个数(a)，范围是([1,p-1])，满足(a^2-n)不是模(p)的二次剩余。
接下来使用类似虚数这种拓展数域的方式，令(omega=sqrt{a^2-n})，这个东西在模(p)的数域下是不存在的。用二元组((a,b))表示(a+bomega)，那么可以得到：
很明显，(C(lfloor{p/p} floor,lfloor{i/p} floor))的值永远为(1),而(C(p\%p,i\%p))只有在(i=0或p)的时候才会是(1)，其他时刻都为(0)，那么式子可以继续化简：
因为(a^{p-1}equiv 1), ((a^2+n)^{frac{p-1}{2}}equiv -1)，所以
所以((a+omega)^{frac{p+1}{2}})就是其中一个(x)，用(p-x)就能得到另一个(x)。
struct Complex {
Complex(LL x, LL y) : x(x), y(y) {}
LL x, y;
};
inline Complex mul(Complex a, Complex b) {
return Complex(a.x*b.x%M + a.y*b.y%M*w%M, a.y*b.x*M+a.x*b.y%M);
}
LL qpow(LL a, LL b, LL M) {
LL ret = 1;
while (b) {
if (b & 1) ret = ret * a % M;
a = a * a % M, b >>= 1;
}
return ret;
}
Complex qpow(Complex a, LL b) {
Complex ret = Complex(1, 0);
while (b) {
if (b & 1) ret = mul(ret, a);
a = mul(a, a), b >>= 1;
}
return ret;
}
pair<LL, LL> solve(LL n, LL M) {
n %= M;
if (!n) return make_pair(1, 1);
if (M == 2) return make_pair(1, 1);
if (qpow(n, (M - 1) >> 1, M) == M - 1) return make_pair(-1,-1);
LL ans, ans1, ans2;
a = rand() % M;
while (!a || qpow((a * a - n + M) % M, (M - 1) >> 1, M)) a = rand() % M;
w = (a * a - n + M) % M;
ans1 = qpow(Complex(a, 1), (M + 1) >> 1).x;
ans2 = M - ans1;
if (ans1 > ans2) swap(ans1, ans2);
return make_pair(ans1, ans2);
}
大步小步(BSGS)
就是在模(p)的情况下求出(log_ab)，非常暴力。
现在考虑的是(a,p)互质的特殊情况，
首先使用Hash表或者std::map存储(b imes a^{i}(0leq ileq lceilsqrt{b}
ceil))，以及对应的(i)，然后枚举(a^{ilceil{sqrt{p}}
ceil}(0leq ilceil{sqrt{p}}
ceilleq p))，如果得到一个值存在于表中，那么直接将指数相减就好了。
namespace BSGS {
map<LL, LL> val_map;
LL log(LL a, LL b, LL M) { // a^x = b (mod M)
val_map.clear();
LL sqrt_m = ceil(sqrt(M));
b %= M;
for (int i = 1; i <= sqrt_m; i++) {
b = b * a % M;
val_map[b] = i;
}
LL vec = qpow(a, sqrt_m, M); b = 1;
for (int i = 1; i <= sqrt_m; i++) {
b = b * vec % M;
if (val_map.count(b)) return (i * sqrt_m - val_map[b] + M) % M;
}
return -1;
}
}
拓展大步小步(EX_BSGS)
现在考虑(a,p)不互质的情况。
如果(b)不能被(g)整除，那么式子无解，因为(frac{a}{g},frac{p}{g})互质，所以一定有(frac{a}{g})在模(frac{p}{g})下的逆元，对式子进行变化：
这样子就得到另一个形式相同的式子，但是(a)和(frac{p}{g})可能依然不互质，需要继续变化。如果最终互质了，就用BSGS进行求解。
namespace EX_BSGS {
LL log(LL a, LL b, LL M) {
if (b == 1 || M == 1) return 0;
LL g = gcd(a, M), cnt = 0, k = 1;
while (g > 1) {
if (b % g) return -1;
cnt++, b /= g, M /= g, k = k * (a / g) % M;
if (k == b) return cnt;
g = gcd(a, M);
}
LL ans2 = BSGS::log(a, b * inv(k, M) % M, M);
if (ans2 == -1) return -1;
else return ans2 + cnt;
}
}