点个赞评个论喵。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、拓展欧几里得解二元一次不定方程
解形如 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。
> 裴蜀定理：方程 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。
即原方程的一组解为 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.费马小定理
在 ppp 为素数且 gcd(a,p)=1\gcd(a, p) = 1gcd(a,p)=1 的情况下：
ap−1≡1(modp)a^{p-1}\equiv 1 \pmod p ap−1≡1(modp)
2.逆元
若
a⋅b≡1(modn)a \cdot b \equiv 1 \pmod n a⋅b≡1(modn)
则 a,ba,ba,b 互为模 nnn 意义下的乘法逆元。
逆元存在的充要条件是 gcd(a,n)=1\gcd(a,n) = 1gcd(a,n)=1。
逆元存在的必要性：
a mod p+b mod p=(a+b) mod pa mod p−b mod p=(a−b) mod pa mod p⋅b mod p=ab mod pa mod pb mod p≠ab mod pa \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
amodp+bmodp=(a+b)modpamodp−bmodp=(a−b)modpamodp⋅bmodp=abmodpbmodpamodp =ba modp
故此需将除法转化为乘法。
逆元的求法
注意到
a⋅ap−2=ap−1≡1(modp)a \cdot a^{p-2}=a^{p-1} \equiv 1 \pmod p a⋅ap−2=ap−1≡1(modp)
由逆元的唯一性可得 aaa 在模 ppp 意义下的乘法逆元为 ap−2a^{p-2}ap−2，可用快速幂求解。
因有 ap−2≡a−1a^{p-2} \equiv a^{-1}ap−2≡a−1，故此逆元常被称为数论倒数。
逆元唯一性证明
若 b1,b2b_1, b_2b1 ,b2 都是 aaa 的逆元，则 ab1≡ab2≡1(modp)a b_1 \equiv a b_2 \equiv 1 \pmod pab1 ≡ab2 ≡1(modp)，
两边同乘 b1b_1b1 得 b1≡b2(modp)b_1 \equiv b_2 \pmod pb1 ≡b2 (modp)，故逆元唯一。
三、组合数学基础
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 或 PnmP_n^mPnm ，下文普遍采用 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)\dbinom{n}{m}(mn )，下文普遍使用 (nm)\dbinom{n}{m}(mn )。
计算公式：
(nm)=Anmm!=n!m!(n−m)!\dbinom{n}{m} = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!} (mn )=m!Anm =m!(n−m)!n!
公式可以理解为，在 AnmA_n^mAnm 的基础上，(nm)\dbinom{n}{m}(mn ) 并不关心两个元素之间的顺序，所以除以 mmm 个元素的全排列 m!m!m! 即可。
特别地，对于 m>nm > nm>n 的情况，Anm=(nm)=0A_n^m = \dbinom{n}{m} = 0Anm =(mn )=0。
组合数公式：
Pascal\mathtt{Pascal}Pascal 恒等式
(nm)=(n−1m)+(n−1m−1)\dbinom{n}{m} = \dbinom{n-1}{m} + \dbinom{n-1}{m-1} (mn )=(mn−1 )+(m−1n−1 )
Lucas\mathtt{Lucas}Lucas 定理
(nm)≡(n mod pm mod p)⋅(⌊n/p⌋⌊m/p⌋)(modp)\dbinom{n}{m} \equiv \dbinom{n \bmod p}{m \bmod p} \cdot \dbinom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p (mn )≡(mmodpnmodp )⋅(⌊m/p⌋⌊n/p⌋ )(modp)
排列组合基础部分常用公式
（1）nnn 个相同元素，分成 kkk 组，每组至少一个，求方案数。
考虑将 k−1k-1k−1 块板子插入至 n−1n-1n−1 个空中，显然答案为 (n−1k−1)\dbinom{n-1}{k-1}(k−1n−1 )。
（2）nnn 个相同元素，分成 kkk 组，每组数量无限制，求方案数。
考虑先拿来 kkk 个元素，此时将（2）转化为（1），易得答案为 (n+k−1n)\dbinom{n+k-1}{n}(nn+k−1 )。
（3）nnn 个相同元素，分成 kkk 组，每组至少 aia_iai 个，求方案数。
考虑拿来 ∑ai\sum a_i∑ai 个元素，每个分 aia_iai 个，转化至（2），再使用（2）的公式可得答案为 (n−∑ain−∑ai+k−1)\dbinom{n-\sum a_i}{n-\sum a_i+k-1}(n−∑ai +k−1n−∑ai )。
（4）在 nnn 个连续的整数中选 kkk 个，两两不相邻的选法有 (n−k+1k)\dbinom{n-k+1}{k}(kn−k+1 ) 种。
（5）nnn 个不相同的物体排列成一个圆，方法有 (n−1)!(n-1)!(n−1)! 种。
（6）nnn 个任意元素排列方式有 n!n1!⋅n2!⋯nk!\dfrac{n!}{n_1! \cdot n_2! \cdots n_k!}n1 !⋅n2 !⋯nk !n! 种。
补充一下二项式定理的内容，证明可以采用数学归纳法解决，这里不多赘述。
(a+b)n=∑k=0n(nk)an−kbk(a+b)^n = \sum\limits_{k=0}^{n} \dbinom{n}{k} a^{n-k} b^k (a+b)n=k=0∑n (kn )an−kbk
3.容斥原理
设 U 中元素有 nnn 种不同的属性，第 iii 种称为 PiP_iPi ，拥有属性 PiP_iPi 的构成集合 SiS_iSi ，则：
∣⋃i=1nSi∣=∑i∣Si∣−∑i<j∣Si∩Sj∣+∑i<j<k∣Si∩Sj∩Sk∣−⋯+(−1)n−1∣S1∩S2∩⋯∩Sn∣\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} i=1⋃n Si =i∑ ∣Si
∣−i<j∑ ∣Si ∩Sj ∣+i<j<k∑ ∣Si ∩Sj ∩Sk ∣−⋯+(−1)n−1∣S1 ∩S2 ∩⋯∩Sn ∣
四、数论常用特殊函数
求 111 到 nnn 之间的与 nnn 互质的数的个数：
ϕ(n)=n⋅∏p∣n(1−1p)\phi(n) = n \cdot \prod\limits_{p \mid n} \left({1 - \dfrac{1}{p}}\right) ϕ(n)=n⋅p∣n∏ (1−p1 )
求 nnn 的正约数之和：
σ(n)=∏p∣n∑i=0epi\sigma(n)=\prod\limits_{p \mid n}\sum\limits_{i=0}^{e}{p^i} σ(n)=p∣n∏ i=0∑e pi
其中 ppp 为 nnn 的不同质因子，eee 为该质因子的指数。
卡特兰数：
Cn=4n−2n+1⋅Cn−1C_{n} = \dfrac{4n-2}{n+1}\cdot C_{n-1} Cn =n+14n−2 ⋅Cn−1
应用：出栈序列数、二叉树形态数、括号序列等
错排问题（全部对不上）：
Dn=(n−1)(Dn−1+Dn−2)D1=0,D2=1D_n=(n-1)(D_{n-1}+D_{n-2})\\D_1=0,D_2=1 Dn =(n−1)(Dn−1 +Dn−2 )D1 =0,D2 =1
