数论综合
_buzhidao_
·
·
算法·理论
排列组合
排列
A_n^m=\frac{n!}{(n-m)!}
在 n 个物品中拿取 m 个，考虑顺序的总排列数量。
其中 n,m\in \Z^+，m \le n。
组合
C_n^m=\frac{n!}{m! \cdot (n-m)!}
在 n 个物品中拿取 m 个，不考虑顺序的总组合数量。
其中 n,m\in \Z^+，m \le n。
也可以表示为 {n \choose m}。
多重组合
在 n 类物品中随意拿取 m 个，不考虑顺序的总组合数量。每类物品数量不限制。
可以表示为 \left( \! {n\choose m} \! \right)。
\left( \! {n\choose m} \! \right) ={n+m-1 \choose n-1}={n+m-1 \choose m}
卡特兰数
卡特兰数
递推公式
C_0=1
C_n={2n \choose n}-{2n \choose n-1}=\frac{1}{n+1}{2n \choose n}
C_n=\frac{C_{n-1} \cdot (4n-2)}{n+1}
公式 & 性质
{n \choose m}={n \choose n-m}
由组合数的意义推得。
{n \choose m}={n-1 \choose m}+{n-1 \choose m-1}
由杨辉三角性质推得。
{n \choose m}=\frac{n}{m}\cdot {n-1 \choose m-1}
由公式推得。
{n \choose m}=\sum_{i=m-1}^{n-1}{i \choose m-1}
由杨辉三角性质推得。
组合意义：从一个长度为 n 的集合 \{1,2,\dots,n\} 中选取一个长度为 m 的子集，固定元素最大值为 i+1。
\sum_{i=0}^n i{n \choose i}=n\cdot 2^{n-1}\pod {=\sum_{i=1}^n 2^{n-1}}
组合意义：一个长度为 n 的集合 \{1,2,\dots,n\} 其子集大小之和，等于包含某个特定元素的子集总数之和。
\sum_{i=0}^k{n \choose i}{m \choose k-i}={n+m \choose k}
组合意义：从两个互不相交的集合的并集中选取一个长度为 k 的子集的数量，等于从两个集合中分别选择 i 和 k-i 个元素的组合总数。
{n \choose m}{m \choose k}={n \choose k}{n-k \choose m-k}
由公式推得。
组合意义：从一个长度为 n 的集合 S 中选取长度分别为 m,k 的两个子集 A,B，满足 B \subseteq A \subseteq S。
等号左边先选择 A，再选择 B；等号后边先选择 B，再选择 A \oplus B。
(x+y)^n=\sum_{i=0}^n{n \choose i}x^iy^{n-i}
二项式定理。
推论
{n \choose m}^2={n \choose m}{n \choose n-m}={2n \choose n}
由公式推得。
欧拉筛法
【模板】线性筛素数
一般情况下，单纯埃氏筛法可以在 300\text{ms} 内跑完 n=10^8，单纯欧拉筛法则需要 750\text{ms} 左右。
但是埃氏筛法在常数过大时甚至需要 2\text{s} 完成。
所以按需选用两种筛法很重要。
核心思想
让每个合数只被其最小质因数筛掉。
\Huge\sum
费马小定理
a^{p-1} \equiv 1 \pmod p
其中，a \in \Z，\gcd(a,p) \neq 0，p 为质数。
欧几里得定理
朴素欧几里得
\gcd(a,b)=\gcd(b,a \bmod b)
证明：
不妨设 d 为 a 和 b 的任意一个公因数，则由同余性质，a \equiv b \equiv 0 \pmod d。
易得 ∀d | \gcd(a,b) 都满足这个性质。
假设 a=k \cdot b +r，有 r=a \bmod b。
所以 a-k\cdot b \equiv r \equiv 0 \pmod d。
代码：
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
复杂度： O(\log)。
（即使 a<b 算法也有效）
扩展欧几里得
贝祖等式
对于任意两个整数 a 和 b，必定存在两个整数 x 和 y，满足以下等式：
ax+by=\gcd(a,b)
使用扩展欧几里得算法能够计算出 x 和 y 的一组值，从而求出其所有值的表达式。
x = x_0+i\cdot \frac{b}{\gcd(a,b)}\\
y = y_0-i\cdot \frac{a}{\gcd(a,b)}
\end{cases}
其中，i \in \Z。
推理过程：
由贝祖等式，
ax+by=\gcd(a,b)
即，
ax+by&=\gcd(b,a \bmod b)\\
&=bx+(a \bmod b)y\\
&=bx+(a-\lfloor\frac{a}{b}\rfloor b)y\\
&=ay+b(x-\lfloor\frac{a}{b}\rfloor y)
\end{aligned}
观察到此时 x 变成了 y，y 变成了 (x-\lfloor\frac{a}{b}\rfloor y)。
利用这个性质，我们就可以递归求解 x 和 y。
时间复杂度同样是 O(\log)。
代码如下：
void exgcd(int a, int b, int &x, int &y){
if(!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= a / b * x;
}
代码在回溯时更新 y 的值。
建议修改成返回结构体。
注意此时 x 可能为负数或 \ge m，所以应当把 x 赋值为 [(x \bmod m + m)\bmod m]。
乘法逆元
定义：对于一个非零元素 a，若存在元素 b，使得 a \cdot b=1，则称 b 为 a 的乘法逆元，记作 a^{-1}。
这里主要讨论模意义下的乘法逆元，即使关于 a \cdot b \equiv 1 \pmod m 成立的 b 的值。
注意 a 与 m 一定互素。
扩展欧几里得
由同余性质:
a \cdot x \equiv 1 \pmod m \iff ax+my \equiv 1 \pmod m
所以求逆元的过程就转变为了求不定方程 ax+my=c 在 a \perp m（a 与 m 互素）且 c=1 时 x 的解。
这样就能用扩展欧几里得计算出 a 乘法逆元 x 的值。
注意此处是 \gcd(a,m)，非 \gcd(a,b)。
费马小定理
a^{p-1} \equiv 1 \pmod p \iff a^{p-2} \equiv a^{-1} \pmod p
由费马小定理推得，可直接求出逆元值。
线性逆元
用于求一串数字对于 \bmod \, m 的逆元。
初始化：1^{-1} \equiv 1 \pmod m。
令 i^{-1} \equiv 1 \pmod m，k=\lfloor\frac{m}{i}\rfloor，r=m \bmod i，则：
m=k \cdot i+r
即：
k \cdot i+r \equiv 0 \pmod m
同乘 i^{-1} \cdot r^{-1}，得：
k \cdot r^{-1} + i^{-1} \equiv 0 \pmod m
i^{-1} \equiv -k \cdot r^{-1} \pmod m
i^{-1} \equiv -\lfloor\frac{m}{i}\rfloor \cdot (m \bmod i)^{-1} \pmod m
i^{-1} \equiv (m-\lfloor\frac{m}{i}\rfloor) \cdot (m \bmod i)^{-1} \pmod m
代码：
inv[1] = 1;
for(int i = 2; i < m; ++ i){
inv[i] = (m - m / i) * inv[m % i] % m;
}
阶乘逆元
核心在于逆推。
这个方法易于理解，而且也能达到和线性逆元类似的效果。
令 s_i 为 i! 的乘法逆元，则存在以下递推关系：
s_n=\frac{1}{n!}
s_i=\frac{1}{i!}=s_{i+1}\cdot (i+1)
其中 i! 可以递推，s_n 可以用扩展欧几里得或费马小定理求。
即：
i^{-1} \equiv s_i \cdot (i-1)! \pmod m
预处理复杂度为 O(n)，查询复杂度为 O(1)。
欧拉函数
欧拉定理
$$
\begin{cases}
\varphi(m) &= m\prod_{p|m}\left(1-\frac{1}{p}\right)\\
\varphi(p) &= p-1\\
\varphi(p^k) &= p^k(1-\frac{1}{p})
\end{cases}
$$
三种求法：
1. 利用积性求解。
* 当 $a$ 与 $b$ 互素时，$\varphi(ab)=\varphi(a)\cdot\varphi(b)$。
* 推论：$\varphi(p^k\cdot q^l)=p^k(1-\frac{1}{p})\cdot q^l(1-\frac{1}{q})
- 利用容斥。
- 利用反演。
应用
费马小定理证明
考虑 \{1,2,3,\dots,p-1\} 与 \{a,2a,3a,\dots,(p-1)a\} 的关系。