rt.
其他模板
点个赞评个论喵。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、裴蜀定理
方程 ax+by=cax + by = cax+by=c 有整数解意味着 gcd(a,b)\gcd(a, b)gcd(a,b) 能整除 ccc。反之亦然。（a,b,ca,b,ca,b,c 均为正整数）
即，gcd(a,b)∣c\gcd(a, b) \mid cgcd(a,b)∣c。
二、拓展欧几里得的应用
解形如 ax+by=cax + by = cax+by=c 的二元一次不定方程。
先行求解 ax+by=gcd(a,b)ax + by = \gcd(a, b)ax+by=gcd(a,b)。
利用递归思想。求解下层递归的 x2,y2x_2,y_2x2 ,y2 ，回代上层。
易得递归边界为 x2=1,y2=0x_2 = 1, y_2 = 0x2 =1,y2 =0。①
因为 x=y2,y=x2−ab⋅y2x = y_2, y = x_2 - \dfrac{a}{b} \cdot y_2x=y2 ,y=x2 −ba ⋅y2 。②
故此可以求出方程 ax+by=gcd(a,b)ax + by = \gcd(a, b)ax+by=gcd(a,b) 的一组解。
由裴蜀定理得 gcd(a,b)∣c\gcd(a, b) \mid cgcd(a,b)∣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 yx0 =gcd(a,b)c ⋅x,y0 =gcd(a,b)c ⋅y。
证明：
①
ax+by=gcd(a,b)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)bx2 +(amodb)y2 =gcd(b,amodb)
⋯\cdots⋯
cxk+dyk=gcd(c,d)=ccx_k+dy_k=\gcd(c, d) = ccxk +dyk =gcd(c,d)=c
此为递归边界，显然 xk=1,yk=0x_k = 1,y_k=0xk =1,yk =0。
②
注意到 a mod b=a−⌊ab⌋⋅ba \bmod b = a - \lfloor \dfrac{a}{b} \rfloor \cdot bamodb=a−⌊ba ⌋⋅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)bx2 +ay2 −⌊ba ⌋⋅b⋅y2 =gcd(b,amodb)。
合并同类项：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)ay2 +b(x2 −⌊ba ⌋⋅y2 )=gcd(b,amodb)。
因为 gcd(a,b)=gcd(b,a mod b)\gcd(a, b) = \gcd(b, a\bmod b)gcd(a,b)=gcd(b,amodb)，所以得出 x=y2,y=x2−⌊ab⌋⋅y2x = y_{2}, y = x_{2}-\lfloor \dfrac{a}{b} \rfloor \cdot y_{2}x=y2 ,y=x2 −⌊ba ⌋⋅y2 。
此法仅能求出一组解。
通解：
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)}x′=x0 +t⋅gcd(a,b)b ,y′=y0 −t⋅gcd(a,b)a 。（ttt 为任意整数）
最小解：
在周期 [1,bgcd(a,b)][1, \dfrac{b}{\gcd(a, b)}][1,gcd(a,b)b ] 或 [0,bgcd(a,b)−1][0, \dfrac{b}{\gcd(a, b)} - 1][0,gcd(a,b)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 modgcd(a,b)b +gcd(a,b)b )modgcd(a,b)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)} + 1xmin =(x0 modgcd(a,b)b +gcd(a,b)b −1)modgcd(a,b)b +1。
求 yminy_{min}ymin 时将 x0x_0x0 替换成 y0y_0y0 ，bgcd(a,b)\dfrac{b}{\gcd(a, b)}gcd(a,b)b 替换成 agcd(a,b)\dfrac{a}{\gcd(a, b)}gcd(a,b)a 即可。
最大解：
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}xmax =ac−b⋅ymin ,ymax =bc−a⋅xmin 。
是否存在正整数解（x,yx, yx,y 均为正整数）：ymax>0y_{max} > 0ymax >0。
正整数解的个数：xmax−xminbgcd(a,b)+1\dfrac{x_{max} - x_{min}}{\frac{b}{\gcd(a, b)}} + 1gcd(a,b)b xmax −xmin +1。
三、组合数学
1.加乘原理
加法原理：
对于一件事，有 nnn 类完成办法，令 aia_iai 表示完成第 iii 种办法的方案数，则总共完成办法为 ∑i=1nai\sum\limits_{i=1}^n a_ii=1∑n ai 。
乘法原理：
对于一件事，有 nnn 个完成步骤，令 aia_iai 表示完成第 iii 个步骤的方案数，则总共完成办法为 ∏i=1nai\prod\limits_{i=1}^n a_ii=1∏n ai 。
2.排列与组合
排列数的定义：
在 nnn 个不同的数中取出 m(m≤n)m(m \leq n)m(m≤n) 个，按任意顺序排列。
排列方案的总数即为排列数，记作 AnmA_n^mAnm 。
计算公式：
Anm=∏i=0m−1(n−i)=n!(n−m)!A_n^m=\prod\limits_{i=0}^{m-1} (n-i)=\dfrac{n!}{(n-m)!} Anm =i=0∏m−1 (n−i)=(n−m)!n!
全排列：
Ann=∏i=0n−1(n−i)=n!A_n^n=\prod\limits_{i=0}^{n-1} (n-i)=n! Ann =i=0∏n−1 (n−i)=n!
这是排列数的一个特殊情况。
公式可以理解为第一个位置可以选 nnn 个，第二个可以选 n−1n-1n−1 个，以此类推，第 mmm 个可以选 n−m+1n-m+1n−m+1 个。
组合数的定义
在 nnn 个不同的数中取出 m(m≤n)m(m \leq n)m(m≤n) 个，组成一个集合。
集合的总数即为组合数，记作 CnmC_n^mCnm 或 (nm)\begin{pmatrix}n\\m\end{pmatrix}(nm )，下文普遍使用(nm)\begin{pmatrix}n\\m\end{pmatrix}(nm )。
计算公式：
(nm)=Anmm!=n!m!(n−m)!\begin{pmatrix}n\\m\end{pmatrix} = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!} (nm )=m!Anm =m!(n−m)!n!
公式可以理解为，在 AnmA_n^mAnm 的基础上，(nm)\begin{pmatrix}n\\m\end{pmatrix}(nm ) 并不关心两个元素之间的顺序，所以除以 mmm 个元素的全排列 m!m!m! 即可。
特别地，对于 m>nm > nm>n 的情况，Anm=(nm)=0A_n^m = \begin{pmatrix}n\\m\end{pmatrix} = 0Anm =(nm )=0。
排列组合基础部分常用公式
（1）nnn 个相同元素，分成 kkk 组，每组至少一个，求方案数。
考虑将 k−1k-1k−1 块板子插入至 n−1n-1n−1 个空中，显然答案为 (n−1k−1)\begin{pmatrix}n-1\\k-1\end{pmatrix}(n−1k−1 )。
（2）nnn 个相同元素，分成 kkk 组，每组数量无限制，求方案数。
考虑先拿来 kkk 个元素，此时将（2）转化为（1），易得答案为 (n+k−1n)\begin{pmatrix}n+k-1\\n\end{pmatrix}(n+k−1n )。
（3）nnn 个相同元素，分成 kkk 组，每组至少 aia_iai 个，求方案数。
考虑拿来 ∑ai\sum a_i∑ai 个元素，每个分 aia_iai 个，转化至（2），再使用（2）的公式可得答案为 (n−∑ain−∑ai+k−1)\begin{pmatrix}n-\sum a_i\\n-\sum a_i+k-1\end{pmatrix}(n−∑ai n−∑ai +k−1 )。
（4）在 nnn 个连续的整数中选 kkk 个，两两不相邻的选法有 (n−k+1k)\begin{pmatrix}n-k+1\\k\end{pmatrix}(n−k+1k ) 种。
