#创作计划# 数论笔记

点个赞评个论喵。

---

一、拓展欧几里得解二元一次不定方程

解形如 $ax + by = c$ 的二元一次不定方程。
先行求解 $ax + by = \gcd(a, b)$。
利用递归思想。求解下层递归的 $x_2,y_2$，回代上层。
易得递归边界为 $x_2 = 1, y_2 = 0$。①
因为 $x = y_2, y = x_2 - \dfrac{a}{b} \cdot y_2$。②
故此可以求出方程 $ax + by = \gcd(a, b)$ 的一组解。
由裴蜀定理得 $\gcd(a, b) \mid c$。

裴蜀定理：方程 $ax + by = c$ 有整数解意味着 $\gcd(a, b)$ 能整除 $c$。反之亦然。（$a,b,c$ 均为正整数）
即，$\gcd(a, b) \mid c$。

即原方程的一组解为 $x_0 = \dfrac{c}{\gcd(a, b)} \cdot x,y_0 = \dfrac{c}{\gcd(a, b)} \cdot y$。

证明：
①
$ax + by = \gcd(a, b)$
$bx_{2}+(a\bmod b)y_{2}=\gcd(b,a\bmod b)$
$\cdots$
$cx_k+dy_k=\gcd(c, d) = c$
此为递归边界，显然 $x_k = 1,y_k=0$。

②
注意到 $a \bmod b = a - \lfloor \dfrac{a}{b} \rfloor \cdot b$。
代入递归方程可得 $bx_{2} + ay_{2} - \lfloor \dfrac{a}{b} \rfloor \cdot b \cdot y_{2} = \gcd(b, a \bmod b)$。
合并同类项：$ay_{2}+b(x_{2}-\lfloor \dfrac{a}{b} \rfloor \cdot y_{2}) = \gcd(b, a \bmod b)$。
因为 $\gcd(a, b) = \gcd(b, a\bmod b)$，所以得出 $x = y_{2}, y = x_{2}-\lfloor \dfrac{a}{b} \rfloor \cdot y_{2}$。

此法仅能求出一组解。

通解：
$x' = x_0 + t\cdot \dfrac{b}{\gcd(a, b)}, y' = y_0 - t\cdot \dfrac{a}{\gcd(a, b)}$。（$t$ 为任意整数）
最小解：
在周期 $[1, \dfrac{b}{\gcd(a, b)}]$ 或 $[0, \dfrac{b}{\gcd(a, b)} - 1]$：
非负整数解 $x_{min} = (x_0 \bmod \dfrac{b}{\gcd(a, b)} + \dfrac{b}{\gcd(a, b)}) \bmod \dfrac{b}{\gcd(a, b)}$。
正整数解 $x_{min} = (x_0 \bmod \dfrac{b}{\gcd(a, b)} + \dfrac{b}{\gcd(a, b)} - 1) \bmod \dfrac{b}{\gcd(a, b)} + 1$。
求 $y_{min}$ 时将 $x_0$ 替换成 $y_0$，$\dfrac{b}{\gcd(a, b)}$ 替换成 $\dfrac{a}{\gcd(a, b)}$ 即可。
最大解：
$x_{max} = \dfrac{c - b \cdot y_{min}}{a}, y_{max} = \dfrac{c - a\cdot x_{min}}{b}$。
是否存在正整数解（$x, y$ 均为正整数）：$y_{max} > 0$。
正整数解的个数：$\dfrac{x_{max} - x_{min}}{\frac{b}{\gcd(a, b)}} + 1$。

二、费马小定理及其求逆元方法

1.费马小定理
在 $p$ 为素数且 $\gcd(a, p) = 1$ 的情况下：

$$a^{p-1}\equiv 1 \pmod p$$

2.逆元
若

$$a \cdot b \equiv 1 \pmod n$$

则 $a,b$ 互为模 $n$ 意义下的乘法逆元。
逆元存在的充要条件是 $\gcd(a,n) = 1$。
逆元存在的必要性：

$$a \bmod p + b \bmod p = (a+b) \bmod p\\a \bmod p - b \bmod p = (a-b) \bmod p\\a \bmod p \cdot b \bmod p = ab \bmod p\\\frac{a \bmod p}{b \bmod p} \neq \frac{a}{b} \bmod p$$

故此需将除法转化为乘法。

逆元的求法
注意到

$$a \cdot a^{p-2}=a^{p-1} \equiv 1 \pmod p$$

由逆元的唯一性可得 $a$ 在模 $p$ 意义下的乘法逆元为 $a^{p-2}$，可用快速幂求解。
因有 $a^{p-2} \equiv a^{-1}$，故此逆元常被称为数论倒数。

逆元唯一性证明
若 $b_1, b_2$ 都是 $a$ 的逆元，则 $a b_1 \equiv a b_2 \equiv 1 \pmod p$，
两边同乘 $b_1$ 得 $b_1 \equiv b_2 \pmod p$，故逆元唯一。

三、组合数学基础

1.加乘原理
加法原理：
对于一件事，有 $n$ 类完成办法，令 $a_i$ 表示完成第 $i$ 种办法的方案数，则总共完成办法为 $\sum\limits_{i=1}^n a_i$。
乘法原理：
对于一件事，有 $n$ 个完成步骤，令 $a_i$ 表示完成第 $i$ 个步骤的方案数，则总共完成办法为 $\prod\limits_{i=1}^n a_i$。
2.排列与组合
排列数的定义：
在 $n$ 个不同的数中取出 $m(m \leq n)$ 个，按任意顺序排列。
排列方案的总数即为排列数，记作 $A_n^m$ 或 $P_n^m$，下文普遍采用 $A_n^m$。
计算公式：

$$A_n^m=\prod\limits_{i=0}^{m-1} (n-i)=\dfrac{n!}{(n-m)!}$$

全排列：

$$A_n^n=\prod\limits_{i=0}^{n-1} (n-i)=n!$$

这是排列数的一个特殊情况。

公式可以理解为第一个位置可以选 $n$ 个，第二个可以选 $n-1$ 个，以此类推，第 $m$ 个可以选 $n-m+1$ 个。

组合数的定义
在 $n$ 个不同的数中取出 $m(m \leq n)$ 个，组成一个集合。
集合的总数即为组合数，记作 $C_n^m$ 或 $\dbinom{n}{m}$，下文普遍使用 $\dbinom{n}{m}$。
计算公式：

$$\dbinom{n}{m} = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!}$$

公式可以理解为，在 $A_n^m$ 的基础上，$\dbinom{n}{m}$ 并不关心两个元素之间的顺序，所以除以 $m$ 个元素的全排列 $m!$ 即可。

特别地，对于 $m > n$ 的情况，$A_n^m = \dbinom{n}{m} = 0$。

组合数公式：
$\mathtt{Pascal}$ 恒等式

$$\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1}$$

$\mathtt{Lucas}$ 定理

$$\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \cdot \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p$$

排列组合基础部分常用公式
（1）$n$ 个相同元素，分成 $k$ 组，每组至少一个，求方案数。
考虑将 $k-1$ 块板子插入至 $n-1$ 个空中，显然答案为 $\dbinom{n-1}{k-1}$。

（2）$n$ 个相同元素，分成 $k$ 组，每组数量无限制，求方案数。
考虑先拿来 $k$ 个元素，此时将（2）转化为（1），易得答案为 $\dbinom{n+k-1}{n}$。

（3）$n$ 个相同元素，分成 $k$ 组，每组至少 $a_i$ 个，求方案数。
考虑拿来 $\sum a_i$ 个元素，每个分 $a_i$ 个，转化至（2），再使用（2）的公式可得答案为 $\dbinom{n-\sum a_i}{n-\sum a_i+k-1}$。

（4）在 $n$ 个连续的整数中选 $k$ 个，两两不相邻的选法有 $\dbinom{n-k+1}{k}$ 种。

（5）$n$ 个不相同的物体排列成一个圆，方法有 $(n-1)!$ 种。

（6）$n$ 个任意元素排列方式有 $\dfrac{n!}{n_1! \cdot n_2! \cdots n_k!}$ 种。

补充一下二项式定理的内容，证明可以采用数学归纳法解决，这里不多赘述。

$$(a+b)^n = \sum\limits_{k=0}^{n} \dbinom{n}{k} a^{n-k} b^k$$

3.容斥原理

设 U 中元素有 $n$ 种不同的属性，第 $i$ 种称为 $P_i$，拥有属性 $P_i$ 的构成集合 $S_i$，则：

$$\begin{aligned} \left| \bigcup_{i=1}^n S_i \right| &= \sum_i |S_i| - \sum_{i<j} |S_i \cap S_j| + \sum_{i<j<k} |S_i \cap S_j \cap S_k| - \cdots \\ &\quad + (-1)^{n-1} |S_1 \cap S_2 \cap \cdots \cap S_n| \end{aligned}$$

四、数论常用特殊函数

求 $1$ 到 $n$ 之间的与 $n$ 互质的数的个数：

$$\phi(n) = n \cdot \prod\limits_{p \mid n} \left({1 - \dfrac{1}{p}}\right)$$

求 $n$ 的正约数之和：

$$\sigma(n)=\prod\limits_{p \mid n}\sum\limits_{i=0}^{e}{p^i}$$

其中 $p$ 为 $n$ 的不同质因子，$e$ 为该质因子的指数。

卡特兰数：

$$C_{n} = \dfrac{4n-2}{n+1}\cdot C_{n-1}$$

应用：出栈序列数、二叉树形态数、括号序列等

错排问题（全部对不上）：

$$D_n=(n-1)(D_{n-1}+D_{n-2})\\D_1=0,D_2=1$$