前言
本篇文章主要是给未来的自己看的。由于证明不想直接给导致丧失思考能力，所以没写。还没写完 qwq~。
知识点
余数与质数：质数筛法，欧拉函数，欧几里得（ex），斐蜀定理，BSGS，同余的性质，逆元。
组合与矩阵：矩阵乘法，矩阵加速，高斯消元，组合数学，容斥原理......
......
详解
质数筛法
埃筛：找到质数，并枚举倍数，用质数的倍数筛掉非质数。
线性筛：用一个数最大的因数（除本身）筛去它。上面筛法的优化，不重复。具体的，枚举最大的因数，在搭配上质数去晒去那个数。
p[1]=1;
for(int i=2;i<=n;i++){
if(!p[i])pri[++cnt]=i;
for(int j=1;i*pri[j]<=n;j++){
p[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
欧拉函数
欧拉函数 \(\phi(n)\) 表示 \(\sum_{i=1}^{n}[\gcd(i,n)=1]\)。
重要性质：
\[\phi(n) = n \times \prod_{d|n}(1-\frac{1}{d}) \]\[\phi(n) \times \phi(m) = \phi(n*m) [\gcd(n,m)=1] \]由第二条性质，我们就可以用线性筛来得到每个数的欧拉函数值。
p[1]=phi[1]=1;
for(int i=2;i<=n;i++){
if(!p[i]) pri[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
p[i*pri[j]]=true;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
欧几里得算法
就是辗转相除法。
\[\gcd(a,b) = \gcd(b,a \bmod b) \]先介绍一下斐蜀定理。
即：对于任意可以写为 \(ax +by = c\) 的方程，如果 \(\gcd(a,b)|c\)，方程一定有整数解。
这样，我们就可以用拓展欧几里得算法来求出方程的解。
拓展欧几里得
\(ax +by = \gcd(a,b)\)
我们需要不断递归，最后求出解。
\[ax + by = \gcd(a,b) \]\[a \bmod b=a-b\times\lfloor\frac{a}{b}\rfloor \]\[bx' + (a-b\times\lfloor\frac{a}{b}\rfloor)y' = \gcd(b,a-a\times\lfloor\frac{a}{b}\rfloor) \]\[bx' + ay'-b\times\lfloor\frac{a}{b}\rfloor y' = \gcd(b,a-a\times\lfloor\frac{a}{b}\rfloor) \]\[ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')= \gcd(b,a-a\times\lfloor\frac{a}{b}\rfloor) \]由此可得，递归的上一层的解 \(x\) 和 \(y\) 与当前层的解 \(x'\) 和 \(y'\) 关系是这样的：\(x=y'\)，\(y=(x'-\lfloor\frac{a}{b}\rfloor y')\)。
BSGS
求解：
\[a^x \equiv b \pmod p \]\(p\) 为质数。
设一个数 \(t=\lceil \sqrt{p}\rceil\)，令 \(x = i \times t -j\)。
\[a^x \equiv b \pmod p \]\[a^{i\times t - j} \equiv b \pmod p \]\[a^{i\times t} \equiv b \times a^j\pmod p \]这样可以暴力枚举 \(j\)，放入 Hash 表中，在枚举 \(i\) 取相等，如果有且为找到的第一个，最小解为 \(i\times t-j\)。
显然，当 \(\gcd(a,p)=1\) 时才有解。
同余的性质
就很简单，不想写。
逆元
当 \(\gcd(a,m)=1\) 时，若 \(ax \equiv 1 \pmod m\)，则我们称 \(x\) 是关于模 \(m\) 的逆元，即为 \(a^{-1}\)。