数论常用定理

Bezout 定理

$a,b$ 不全为 $0$，则 $\exists x,y,ax+by=\gcd(a,b)$，$x,y$ 为整数。

求出一组可行解的方法

可以使用 exgcd 求出一组可行解。

$b\ne 0$ 时，$ax_1+by_1=(a,b)=(b,a\bmod b)=bx_2+(a\bmod b)y_2$. 所以

$$ ax_1+by_1=ay_2+bx_2-\left\lfloor\frac{a}{b}\right\rfloor\times by_2=ay_2+b(x_2-\left\lfloor\frac{a}{b}\right\rfloor y_2) $$

不断递归，直到推到边界 $b=0,x=1,y=0$ 即可。

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

Fermat 小定理

$p\in \mathrm{prime},\gcd(a,p)=1$，则 $a^{p-1}\equiv 1(\bmod p~)$.

可以用剩余系证明，不再赘述。

Euler 定理

若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1(\bmod m~)$.

扩展 Euler 定理

$$a^b\equiv \begin{cases} a^{b\bmod \varphi(m)}& \gcd(a,m)=1\\ a^b& \gcd(a,m)=1,b<\varphi(m),~~~(\bmod m~)\\ a^{(b\bmod \varphi(m))+\varphi(m)}& \gcd(a,m)\ne 1,b\ge \varphi(m) \end{cases}$$

乘法逆元

主要需要了解两种求解乘法逆元的方式（快速幂和扩展欧几里得），以及线性求逆元。

这里介绍一下线性求逆元的方法：

考虑我们已经知道了 $1\sim i-1$ 的逆元，现在要求出 $\mathrm{inv}(i)$.

我们考虑 $p=ki+j$，则 $(ki+j)\bmod p=0$.

两边同时乘 $i,j$ 的逆元，可以得到

$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor(p\bmod i)^{-1}$，可以使用递推求逆元。

另外还要知道一个可以求出任意 $n$ 个数的逆元，考虑先求前缀积，然后从后往前倒推即可。

CRT

可以用来求解一元线性同余方程组。

构造过程如下：

1. 计算所有模数的乘积 $n$.
2. 对于第 $i$ 个方程：计算 $m_i=\frac{n}{n_i}$，算出 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$，最后计算 $c_i=m_im_i^{-1}$，注意此处不要对 $n_i$ 取模。
3. 方程在模 $n$ 意义下的唯一解是：

$$ x=\sum_{i=1}^ka_ic_i(\bmod n~) $$

EXCRT

如果模数不互质，就没法求解逆元了。

我们先考虑如果只有两个同余方程的情况。

这个时候，我们可以将同余方程转换成不定方程 $x=m_1p+a_1=m_2q+a_2,m_1p-m2_q=a_2-a_1$。此时，可以用扩展欧几里得算出一组可行解或判断无解。

而最终，我们可以把 $n$ 个式子按照顺序两两合并。

Lucas 定理

考虑 $p\in\mathrm{prime}$，求解 $C_n^m$. $n,m\le 10^9,p\le 10^5$。

这个时候可以使用 Lucas 定理求解，$C_n^m\equiv C_{\left\lfloor\frac{n}{p}\right\rfloor}^{\left\lfloor\frac{m}{p}\right\rfloor}\times C_{\left\lfloor n\bmod p\right\rfloor}^{\left\lfloor m\bmod p\right\rfloor}$。直接求解，复杂度可以接受。

证明可以看 这里。

组合计数

组合恒等式

$$ C_n^k=C_n^{n-k}\\ C_{n+1}^k=C_n^{k-1}+C_n^k\\ kC_{n}^k=nC_{n-1}^{k-1}\\ C_n^kC_k^m=C_n^mC_{n-m}^{k-m}=C_{n}^{k-m}C_{n-k+m}^m(m\le k\le n)\\ \sum_{i=0}^nC_{n}^i=2^n\\ \sum_{i=0}^n(-1)^iC_{n}^i=0,(n\ge 1)\\ \sum_{i=m}^nC_{i}^m=C_{n+1}^{m+1}\\ \sum_{i=n}^{n+m}C_i^k=C_{n+m+1}^{k+1}-C_{n}^{k+1}\\ \sum_{i=0}^pC_{n}^{i}C_m^{p-i}=C_{n+m}^p $$

例题 $1$

证明：$\sum_{k=1}^n kC_{n}^k=n2^{n-1}$.

思路：$\mathrm{LHS}=\sum nC_{n-1}^{k-1}$，利用此式得证。

例题 $2$

证明：$\sum_{k=1}^n 2^kC_n^kC_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}=C_{2n+1}^n$

解：右边的式子可以理解成有 $2n+1$ 个小球选$n$ 个，而左边可以理解成枚举 $k$ 个球是单独选的，而 $C_{n-k}^{\left\lfloor\frac{n-k}{2}\right\rfloor}$ 就是剩下来的两两配对的方案数。

例题 $3$

题目：Selecting Teams

问题等价于求 $\sum_{i=1}^kC_{n}^i\times \sum_{j=1}^ijC_{i}^j=\sum_{i=1}^kC_n^ii2^{i-1}$，根据模数只需要计算 $i\le 23$ 的答案即可。

二项式定理

$$ (a+b)^n=\sum_{k=0}^nC_n^ka^kb^{n-k}\\ (x+1)^n=\sum_{k=0}^nC_n^kx^k $$

组合数取模

只写几个难的。

$m\le n\le 10^9,P\le 10^5,P\in \mathrm{prime}$: Lucas 定理.

$m\le n\le 10^9,P=p^c\le 10^5,p\in \mathrm{prime}$: 考虑将 $n!,m!,(n-m)!$ 分开求解。计算 $n!$，显然可以是以 $P$ 为一个循环节计算的。关键是求解 $m!,(n-m)!$ 的时候，可能不存在逆元。

我们把数表示成 $k\times p^x$，因为 $k$ 存在逆元，所以直接乘起来，然后记录 $p$ 的因子个数。这个过程可以把数变成原来的 $\frac{1}{p}$，递归即可。

P.S.: 如果 $P$ 不能表示成 $p^c$，就可以对 $P$ 进行质因数分解，用 CRT 合并。

二项式反演

$$ \sum_{k=0}^{n}(-1)^kC_{n}^k=e(n+1) $$