数论笔记

userId_undefined
古希腊掌管AC和WA的神
时间刺客空间掌握者时空双修者出道萌新荣耀黄金快乐小狗

2026-08-24 15:19:38

发布于：上海

31阅读
0回复
0点赞

rt.
其他模板
点个赞评个论喵。

一、裴蜀定理

方程 ax+by=cax + by = c 有整数解意味着 gcd⁡(a,b)\gcd(a, b) 能整除 cc。反之亦然。（a,b,ca,b,c 均为正整数）
即，gcd⁡(a,b)∣c\gcd(a, b) \mid c。

二、拓展欧几里得的应用

解形如 ax+by=cax + by = c 的二元一次不定方程。
先行求解 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)。
利用递归思想。求解下层递归的 x2,y2x_2,y_2，回代上层。
易得递归边界为 x2=1,y2=0x_2 = 1, y_2 = 0。①
因为 x=y2,y=x2−ab⋅y2x = y_2, y = x_2 - \dfrac{a}{b} \cdot y_2。②
故此可以求出方程 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b) 的一组解。
由裴蜀定理得 gcd⁡(a,b)∣c\gcd(a, b) \mid c。
即原方程的一组解为 x0=cgcd⁡(a,b)⋅x,y0=cgcd⁡(a,b)⋅yx_0 = \dfrac{c}{\gcd(a, b)} \cdot x,y_0 = \dfrac{c}{\gcd(a, b)} \cdot y。

证明：
①
ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)
bx2+(a mod b)y2=gcd⁡(b,a mod b)bx_{2}+(a\bmod b)y_{2}=\gcd(b,a\bmod b)
⋯\cdots
cxk+dyk=gcd⁡(c,d)=ccx_k+dy_k=\gcd(c, d) = c
此为递归边界，显然 xk=1,yk=0x_k = 1,y_k=0。

②
注意到 a mod b=a−⌊ab⌋⋅ba \bmod b = a - \lfloor \dfrac{a}{b} \rfloor \cdot b。
代入递归方程可得 bx2+ay2−⌊ab⌋⋅b⋅y2=gcd⁡(b,a mod b)bx_{2} + ay_{2} - \lfloor \dfrac{a}{b} \rfloor \cdot b \cdot y_{2} = \gcd(b, a \bmod b)。
合并同类项：ay2+b(x2−⌊ab⌋⋅y2)=gcd⁡(b,a mod 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 mod b)\gcd(a, b) = \gcd(b, a\bmod b)，所以得出 x=y2,y=x2−⌊ab⌋⋅y2x = y_{2}, y = x_{2}-\lfloor \dfrac{a}{b} \rfloor \cdot y_{2}。

此法仅能求出一组解。

通解：
x′=x0+t⋅bgcd⁡(a,b),y′=y0−t⋅agcd⁡(a,b)x' = x_0 + t\cdot \dfrac{b}{\gcd(a, b)}, y' = y_0 - t\cdot \dfrac{a}{\gcd(a, b)}。（tt 为任意整数）
最小解：
在周期 [1,bgcd⁡(a,b)][1, \dfrac{b}{\gcd(a, b)}] 或 [0,bgcd⁡(a,b)−1][0, \dfrac{b}{\gcd(a, b)} - 1]：
非负整数解 xmin=(x0 mod bgcd⁡(a,b)+bgcd⁡(a,b)) mod bgcd⁡(a,b)x_{min} = (x_0 \bmod \dfrac{b}{\gcd(a, b)} + \dfrac{b}{\gcd(a, b)}) \bmod \dfrac{b}{\gcd(a, b)}。
正整数解 xmin=(x0 mod bgcd⁡(a,b)+bgcd⁡(a,b)−1) mod bgcd⁡(a,b)+1x_{min} = (x_0 \bmod \dfrac{b}{\gcd(a, b)} + \dfrac{b}{\gcd(a, b)} - 1) \bmod \dfrac{b}{\gcd(a, b)} + 1。
求 yminy_{min} 时将 x0x_0 替换成 y0y_0，bgcd⁡(a,b)\dfrac{b}{\gcd(a, b)} 替换成 agcd⁡(a,b)\dfrac{a}{\gcd(a, b)} 即可。
最大解：
xmax=c−b⋅ymina,ymax=c−a⋅xminbx_{max} = \dfrac{c - b \cdot y_{min}}{a}, y_{max} = \dfrac{c - a\cdot x_{min}}{b}。
是否存在正整数解（x,yx, y 均为正整数）：ymax>0y_{max} > 0。
正整数解的个数：xmax−xminbgcd⁡(a,b)+1\dfrac{x_{max} - x_{min}}{\frac{b}{\gcd(a, b)}} + 1。

三、组合数学

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

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

全排列：

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

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

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

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

(nm)=Anmm!=n!m!(n−m)!\begin{pmatrix}n\\m\end{pmatrix} = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!}

公式可以理解为，在 AnmA_n^m 的基础上，(nm)\begin{pmatrix}n\\m\end{pmatrix} 并不关心两个元素之间的顺序，所以除以 mm 个元素的全排列 m!m! 即可。

特别地，对于 m>nm > n 的情况，Anm=(nm)=0A_n^m = \begin{pmatrix}n\\m\end{pmatrix} = 0。

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

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

（3）nn 个相同元素，分成 kk 组，每组至少 aia_i 个，求方案数。
考虑拿来 ∑ai\sum a_i 个元素，每个分 aia_i 个，转化至（2），再使用（2）的公式可得答案为 (n−∑ain−∑ai+k−1)\begin{pmatrix}n-\sum a_i\\n-\sum a_i+k-1\end{pmatrix}。

（4）在 nn 个连续的整数中选 kk 个，两两不相邻的选法有 (n−k+1k)\begin{pmatrix}n-k+1\\k\end{pmatrix} 种。

userId_undefined
去预览
0/2000

全部评论 7

热门讨论