5 数论
数论
高精度
高精度加减乘除
1 | const int N = 1e5; //最大容量 |
高精度取模（秦九韶算法）
1 | string s; // 输入的大数字 |
快速幂
快速幂 快速幂取模
1 | long long quickpow(long long a, long long n) // 快速幂 a^n |
矩阵快速幂
1 | /*求矩阵a的k次方*/ |
最大公约数-欧几里得算法（GCD）
$$
当a>b,则\gcd(a,b)=\gcd(b,a\bmod b)
$$
1 | int gcd(int a, int b) |
质数
判断素数-试除法
1 | bool prime(int x) |
分解质因数
$$
n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_s^{\alpha_s},p_1<p_2<p
_3<\dots<p_S
$$
1 | const int N = 500005; |
筛法
埃氏筛法
1 | const int N = 100000010; // 最大 |
线性筛
1 | //注意空间，prim有效从下标1开始 |
欧拉函数
**欧拉函数 **$\varphi(n)$ 指小于 $n$ ，并且与 $n$ 互质的数的个数。
$\varphi ( n ) = \sum\limits _ { i = 1 } ^ { n } [ \gcd ( i , n ) = 1 ]$
性质： $\sum\limits _ { d | n } \varphi ( d ) = n$
- 当 $n$ 为质数，$\varphi (n)=p-1$
- 当 $p$ 为质数，$\varphi (p^k)=(p-1)*p^{k-1}$
- 当 $n$ 为合数，$\varphi (n)=s*\prod \limits_{i=1}^s{\frac{p_i-1}{pi}}$
- $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_s^{\alpha_s},p_1<p_2<p
_3<\dots<p_S$
- $n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}\dots p_s^{\alpha_s},p_1<p_2<p
求单个欧拉函数，代码使用试除法，多个使用线性筛。
1 | // 求单个欧拉函数，试除法 |
约数
约数个数定理：若 $n=\prod \limits_{i=1}^s{p_i^{\alpha_i}}$ ，约数个数 $d(n)=\prod \limits_{i=1}^s{(\alpha_i+1)}$
结论： $d(ij)=\sum\limits_{x|i} \sum\limits_{y|j}[\gcd(x,y)=1]$ （使用和式的变换、莫比乌斯反演）
约数分解规则
- 总是先从 $i$ 中取质因子（唯一性）
- 如果 $i, j$ 中质因子雷同，则把 $i$ 中的该质因子变成 $1$ （互质性）
约数和定理：若 $n=\prod \limits_{i=1}^s{p_i^{\alpha_i}}$ ，约数和 $f(n)=\prod \limits_{i=1}^s{\sum_{j=0}\limits^{\alpha_{i}}{p_i^j}}$
莫比乌斯函数
莫比乌斯函数：$\begin{align*}\begin{split}\mu(n)= \left {\begin{array}{lr}1,& n=1\0,& n含相同质因子\(-1)^s,& s为n的不同质因子的个数\end{array}\right.\end{split}\end{align*}$
性质： $\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]$
同余式
若 $a,b$ 模 $m$ 余数相同，则 $a,b$ 模 $m$ 同余。
即 $ a\equiv b(\bmod m)$
费马小定理
若 $p$ 为质数，且 $a,p$ 互质，则 $a^{p-1}\equiv (\bmod p)$
乘法逆元（费马小定理）
若 $a,p$ 互质，且满足同余方程 $ax\equiv 1(\bmod p)$，则 $x$ 为 $a$ 模 $p$ 的乘法逆元，记作 $a^{-1}$；
若 $p$ 为质数，根据费马小定理可知 $a^{p-2}\times a \equiv (\bmod p)$， $x=a^{p-2}(\bmod p)$；
代码使用快速幂取模求$a^{p-2}(\bmod p)$。
剩余系
剩余系（同余系）：给定一个正整数 $n$ ，把所有整数根据模 $n$ 的余数 $r∈[0,n -1]$ 分为 $n$ 类，每一类表示为 $C_r = nx +r$ 的形式，这类数所构成的一个集合称为模 $n$ 的剩余类。
完全剩余系（完系）：给定一个正整数 $n$ ，有 $n$ 个不同的模 $n$ 的剩余类，从这 $n$ 个不同的剩余类中各取出一个元素，总共 $n$ 个数,将这些数构成一个新的集合，则称这个集合为模 $n$ 的完全剩余系。
简化剩余系（缩系）：给定一个正整数 $n$ ，有 $\varphi (n)$ 个不同的模 $n$ 的余数 $r$ 与 $n$ 互质的剩余类，从这 $\varphi(n)$ 个剩余类中各取出一个元素，总共 $\varphi(n)$ 个数,将这些数构成一个新的集合，则称这个集合为模 $n$ 的简化剩余系。
欧拉定理
若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv 1(\bmod m)$；
当 $m$ 为质数时，由于 $\varphi (m)=m-1$ ，带入欧拉定理可得费马小定理 $a^{m-1}\equiv m$ ；
扩展欧拉定理
- 当 $b$ 小时，直接快速幂；
- 当 $b$ 大时，先降，再快速幂；
$a^b=\begin{align*}\begin{split} \left {\begin{array}{lr}a^b,& b<\varphi(m)\a^{b \ \bmod \ \varphi(m)+\varphi(m)},& b\ge\varphi(m)\end{array}\right.\end{split}\end{align*} ,(\bmod m)$
代码：欧拉函数+高精度取模+快速幂取模
1 | typedef long long ll; |
威尔逊定理
$(p-1)!\equiv -1(\bmod p) \Longleftrightarrow p$ 为质数
- 推论
- 若 $p$ 是质数，则 $(p-1) !+1 \equiv 0(\bmod p)$
- 若 $p$ 是大于 $4$ 的合数，则 $(p-1) ! \equiv 0(\bmod p)$
- $p=1$，$(1-1)! \equiv 0(\bmod1)$；
- $p=4$，$(4-1)! \equiv 2(\bmod 4)$；
裴蜀定理
裴蜀定理：一定存在整数 $x,y$ ，满足 $ax+by=gcd(a,b)$ ；
推广：$\sum {i=1}^{n}A{i}X_{i}=gcd(A_{1},A_{2}, \cdots ,A_{n})$
扩展欧几里得定理
$Q$ ：求 $ax+by=gcd(a,b)$ 一组整数解
当 $b=0$ 时，$ax+by=a$，则 $x=1$，$y=0$
当 $b\neq 0$时，由裴蜀定理
$gcd(a,b)=ax+by$
$gcd(b,a%b)=bx_1+(a%b)y_1=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)$
递推公式：$x_n=y_{n-1},y_n=x_{n-1}-\lfloor\frac{a}{b}\rfloor y_{n-1}$
求得特解 $x_0,y_0$；
通解：$\begin{align*}\begin{split} \left {\begin{array}{lr}x=x_0+\frac{b}{gcd(a,b)}*k\y=y_0-\frac{a}{gcd(a,b)}k\end{array}\right.\end{split}\end{align} (考虑ax+by=0构造)$
求最靠近原点的一组特解 $x_2,y_2$
则需满足条件 $x_2+y2$
求特解代码
1 | int exgcd(int a, int b, int &x, int &y) // a>=b 注意数值范围 |
不定方程
$Q$ ：求 $ax+by=c$ 一组整数解
若 $gcd(a,b)\nmid c$ ，则无整数解；
若 $gcd(a,b)\mid c$，则先求 $ax+by=gcd(a,b)$ 整数解，然后乘以相应倍数 $\frac{c}{gcd(a,b)}$；
转化为扩展欧几里得定理
同余方程
$ax \equiv b(\bmod m)$
$ax=m(-y)+b$
$ax+my=b$
转化为不定方程
乘法逆元（通用）
若 $a,m$ 互质，求 $ax \equiv 1(\bmod m)$ 的解 $x$ ；
转化为不定方程即 $ax+my=1$
使用扩展欧几里得算法的到 $ax+my=gcd(a,m)$ 解 $x$ ；
最终答案：$(x % m+m)% m$ ，“模加模”保证得到最小正整数；
中国剩余定理（CRT）
求解线性同余方程
$\left{ \begin{matrix} x \equiv r_{1}(\bmod m_{1})\ x \equiv r_{2}(\bmod m_{2})\ \vdots\ x \equiv r_{n}(\bmod m_{n})\ \end{matrix} \right.$
其中模数 $m_1, m_2,… , m_n$为 两两互质的整数,求 $x$ 的最小非负整数解。
- 计算所有模数的积 $M$
- 计算第 $i$ 个方程的 $c_{i}=\frac{M}{m_{i}}$
- 计算 $c_{i}$ 在模 ${m}{i}$ 意义下的逆元 $c{i}^{-1}$
- $x=\sum_{i=1}^{n} r_{i} c_{i} c_{i}^{-1}(\bmod M)$
1 | typedef long long ll; |
扩展中国剩余定理（EXCRT）
求解线性同余方程
$\left{ \begin{matrix} x \equiv r_{1}(\bmod m_{1})\ x \equiv r_{2}(\bmod m_{2})\ \vdots\ x \equiv r_{n}(\bmod m_{n})\ \end{matrix} \right.$
其中模数 $m_1, m_2,\dots, m_n$ 不一定 为 两两互质的整数,求 $x$ 的最小非负整数解。
前两个方程： $x \equiv r_{1}\left(\bmod m_{1}\right), x \equiv r_{2}\left(\bmod m_{2}\right)$
转化为不定方程： $x = m_{1} p+r_{1} = m_{2} q+r_{2}$
则 $m_{1} p-m_{2} q = r_{2}-r_{1}$
由裴蜀定理，当 $\operatorname{gcd}\left(m_{1}, m_{2}\right) \nmid\left(r_{2}-r_{1}\right)$ 时，无解
当 $\operatorname{gcd}\left(m_{1}, m_{2}\right) \mid\left(r_{2}-r_{1}\right)$ 时，有解
由扩欧算法，得特解 $p = p * \frac{r_{2}-r_{1}}{g c d}, q = q * \frac{r_{2}-r_{1}}{g c d}$
其通解 $P = p+\frac{m_{2}}{g c d} * k, Q = q-\frac{m_{1}}{g c d} * k$
所以 $x = m_{1} P+r_{1} = \frac{m_{1} m_{2}}{g c d} * k+m_{1} p+r_{1}$
前两个方程等价合并为一个方程 $x \equiv r(\bmod m)$
其中 $r=m_1p+r_1，m=lcm(m_1,m_2) $
所以 $n$ 个同余方程只要合并 $n-1$ 次, 即可求解
1 | typedef long long ll; |
BSGS算法
给定整数 $a,b,p$，其中 $a,p$ 互质，
求满足 $a^x \equiv b(\bmod p)$ 最小非负整数 $x$
扩展BSGS算法
线性方程
高斯消元法
矩阵的初等行变换
- 交换两行；
- 把某一行乘一个**非 $0$ **的数；
- 把某行的若干倍加到另一行上去；
先把系数矩阵消成上三角矩阵，再从下到上回代求解
$\left[\begin{array}{ccccccc}
1 & \mathrm{a}{12}^{\prime} & a{13}^{\prime} & a_{14}^{\prime} & \cdots & a_{1 n}^{\prime} & b_{1}^{\prime} \
& 1 & a_{23}^{\prime} & a_{24}^{\prime} & \cdots & a_{2 n}^{\prime} & b_{2}^{\prime} \
& & 1 & a_{34}^{\prime} & \cdots & a_{3 n}^{\prime} & b_{3}^{\prime} \
& & & \ddots &\ddots & \vdots & \vdots \
& & & &1 & a_{n-1, n}^{\prime} & b_{n-1}^{\prime} \
& & & & & 1 & \mathrm{~b}_{n}^{\prime}
\end{array}\right]$
- 枚举主元, 找到主元下面系数不是 $0$ 的一行；
- 用变换1, 把这一行与主元行交换；
- 用变换2, 把主元系数变成 $1$ ；
- 用变换3, 把主元下面的系数变成 $0$ 。
组合数
递推法（杨辉三角）
时间复杂度： $O(n^2)$
-
$C _ { n } ^ { 0 } = C _ { n } ^ { n } = 1$
-
$C _ { n } ^ { m } = C _ { n } ^ { n - m }$
-
$C _ { n } ^ { m } = C _ { n - 1 } ^ { m } + C _ { n - 1 } ^ { m - 1 }$
1 | // 调用C[n][m]即可 |
快速幂求组合数
时间复杂度： $O(n\log p)$
- $C _ { n } ^ { m } = \frac { n ! } { ( n - m ) ! m ! }$
开两个数组分别存模意义下的阶乘和阶乘的逆元
用 $f[x]$ 存 $x!(\bmod p)$ 的值
用 $g[x]$ 存 $(x!)^{-1}(\bmod p)$ 的值，使用费马小定理和快速幂求逆元
费马小定理： $a \cdot ( a ^ { p - 2 } ) = 1 ( \bmod p )$
$g[x]$ 递推公式： $\frac { 1 } { i! } ( \bmod p ) = \frac { 1 } { i } \times \frac { 1 } { ( i - 1 ) ! } ( \bmod p ) = i^{p-2} * g [ i - 1 ] (\bmod p)$
查询时使用： $C _ { n } ^ { m } ( \bmod p ) = f [ n ] * g [ n - m ] * g [ m ] ( \bmod p )$
1 | typedef long long ll; |
卢卡斯定理（Lucas）
时间复杂度： $O(p\log p + \log_p n)$
$C _ { n } ^ { m } = C _ { n / p } ^ { m/p } C _{n\bmod p} ^{m \bmod p} ( \bmod p )$ ，其中 $p$ 为质数
$n\bmod p$和 $n\bmod p$ 一定是小于 $p$ 的数，可以直接求解， $ C _ { n / p } ^ { m/p }$ 可以继续用 Lucas定理 求解。
边界条件：当 $m=0$ 时，返回 $1$ 。
证明：
- 引理1： $C _ { p } ^ { x } = 0 ( \bmod p ) , 0 \lt x \lt p$
- $C _ { p } ^ { x } = \frac { p ! } { x ! ( p - x ) ! } = \frac { p ( p - 1 ) ! } { x ( x - 1 ) ! ( p - x ) ! } = \frac { p } { x } C _ { p - 1 } ^ { x - 1 }$
- $C _ { p } ^ { x } = p \cdot i n v ( x ) { C _ { p - 1 } ^ { x - 1 } } = 0 ( \bmod p )$
- 引理2： $( 1 + x ) ^ { p } = 1 + x ^ { p } ( \bmod p )$
- 二项式定理知： $( 1 + x ) ^ { p } = \sum _ { i = 0 } ^ { p } C _ { p } ^ { i } x ^ { i }$
- 由上一证明知，只剩 $i=0,p$ 两项，得证。
- 证明：
$( 1 + x ) ^ { n } \equiv \sum _ { i = 0 } ^ { n } C _ { n } ^ { i } x ^ { i } ( m o d p ) – ( 1 )$
$\begin{aligned}
(1+x)^{n} & \equiv(1+x)^{a p+b} \
& \equiv\left((1+x)^{p}\right)^{a} \cdot(1+x)^{b} \
& \equiv\left(1+x^{p}\right)^{a} \cdot(1+x)^{b} \
& \equiv \sum_{i=0}^{a} C_{a}^{i} x^{i p} \cdot \sum_{j=0}^{b} C_{b}^{j} x^{j}(\bmod p)–(2)
\end{aligned}$
$(1)$ 中 $x ^ { m }$ 的系数为 $C_{n}^{m}$
$(2)$ 中 $x^m =x^{cp} \cdot x^d$ 的系数为 $C _ { a } ^ { c } C _ { b } ^ { d }$
则： $C _ { n } ^ { m } = C _ { a } ^ { c } C _ { b } ^ { d } ( \bmod p )$
即： $C _ { n } ^ { m } = C _ { n / p } ^ { m/p } C _{n\bmod p} ^{m \bmod p} ( \bmod p )$
1 | typedef long long ll; |
线性筛+高精度求组合数（单个）
时间复杂度： $O(mnN)$ $N$ 为数字位数
$n!$ 中 $p$ 的个数 $s = \frac { n } { p } + \frac { n } { p ^ { 2 } } + \frac { n } { p ^ { 3 } } + \cdots$
1 | // N为组合数n的最大大小 |
递推法+高精度（单个）
时间不推荐，推荐 前面那个 线性筛+高精度求组合数（单个）
时间复杂度： $O(mnN)$ $N$ 为数字位数
1 | // 组合数的最大数位 |
组合数命名空间（快速幂）
1 | typedef long long i64; |
隔板法
- 求线性不定方程的整数解的组数
- 求相同元素分组的方案数
- 现有 $n$ 个完全相同的元素，将其分为 $k$ 组，保证每组至少有 $1$ 个元素，一共有多少种分法？
把 $n$ 个相同的球排成一行，有 $n-1$ 个空；
拿 $k-1$ 块板子插入到 $n-1$ 个空里，把球分成 $k$ 组；
即在 $n-1$ 个空里选择 $k-1$ 个空插板子，所以答案就是 $C_{n-1}^{k-1}$ ；
？1 正整数和的组数 若 $x _ { i } \geq 1$ ，求 $x _ { 1 } + x _ { 2 } + \cdots + x _ { k } = n$ 的整数解的组数。 $C_{n-1}^{k-1}$
？2 非负整数和的组数 若 $x _ { i } \geq 0$ ，求 $x _ { 1 } + x _ { 2 } + \cdots + x _ { k } = n$ 的整数解的组数。 $C _ { n + k - 1 } ^ { k - 1 }$
令 $y_i=x_i+1$ ，则 $y _ { i } \geq 1$ ；
则 转化为 $y _ { 1 } + y _ { 2 } + \cdots + y _ { k } = n + k = m$
转化为 ？1 ，答案为 $C _ { m - 1 } ^ { k - 1 } = C _ { n + k - 1 } ^ { k - 1 }$
？3 不同下界整数和的组数 求 $x _ { 1 } + x _ { 2 } + \cdots + x _ { k } = n$ 的整数解的组数，其中 $x _ { i } \geq a _ { i } \geq 0 $ ，$\sum a _ { i } \leq n$ $C _ { n - \sum a _ { i } + k -1} ^ { k - 1 }$
令 $y _ { i } = x _ { i } - a _ { i } + 1$ ，则 $y _ { i } \geq 1$ ；
则 转化为 $y _ { 1 } + y _ { 2 } + \cdots + y _ { k } = n - \sum a _ { i } + k = m$
转化为 ？1 ，答案为 $C _ { m - 1 } ^ { k - 1 } = C _ { n - \sum a _ { i } + k -1} ^ { k - 1 } $
卡特兰数（Catalan）
两种操作，一种操作数不能超过另外一种操作数，或者两种操作不能有交集，这些操作的合法方案数，通常是卡特兰数。
以走网格为例，从格点 $(0,0)$ 走到格点 $(n,n)$ ，只能向右或向上走，并且不能越过对角线的路径的条数，就是卡特兰数，记为 $H_n$ 。
- 组合数： $H _ { n } = C _ { 2 n } ^ { n } - C _ { 2 n } ^ { n - 1 }$
- 组合数： $H _ { n } = \frac { 1 } { n + 1 } C _ { 2 n } ^ { n }$
- 递推计算： $H _ { n } = \frac { 4 n - 2 } { n + 1 } H _ { n - 1 }$
先求路径总数：在 $2n$ 次移动中选 $n$ 次向右移动，即 $C_{2n}^{m}$ ，再求非法路径，即越过对角线的路径；
再求非法路径，即越过对角线的路径：
把 $y=x+1$ 这条线画出来，碰到即说明是一条非法路径。所有的非法路径与这条线有至少一个交点，把第一个交点设为 $(a,a+1)$ ；
把 $(a,a+1)$ 之后的路径全部按照 $y=x+1$ 这条线对称过去，这样，最后的终点就会变成 $(n-1,n+1)$ ；
所有非法路径对称后都唯一对应着一条到 $(n-1,n+1)$ 的路径，所以非法路径数就是 $C _ { 2 n } ^ { n - 1 }$ ,合法路径数就是 $C _ { 2 n } ^ { n } - C _ { 2 n } ^ { n - 1 }$ 。
$\begin{align}H_{n}&=C _ { 2 n } ^ { n } - C _ { 2 n } ^ { n - 1 } \&= \frac { ( 2 n ) ! } { n ! n ! } - \frac { ( 2 n ) ! } { ( n + 1 ) ! ( n - 1 ) ! }\&= \frac { ( 2 n ) ! } { n ! ( n - 1 ) ! } ( \frac { 1 } { n } - \frac { 1 } { n + 1 } ) \&= \frac { ( 2 n ) ! } { n ! n ! ( n + 1 ) } \&= \frac { 1 } { n + 1 } C _ { 2 n } ^ { n }\end{align}$
Catalan应用
-
一个有 $n$ 个 $0$ 和 $n$ 个 $1$ 组成的字串，且所有的前缀字串皆满足 $1$ 的个数不超过 $0$ 的个数。这样的字串个数有多少？
-
包含 $n$ 组括号的合法运算式的个数有多少？
-
一个栈的进栈序列为 $1,2,3，…，n$ ，有多少个不同的出栈序列？
-
$n$ 个结点可构造多少个不同的二叉树？
-
在圆上选择 $2$ 个点，将这些点成对连接起来使得所得到的 $n$ 条弦不相交的方法数？
-
通过连结顶点而将 $n+2$ 边的凸多边形分成n个三角形的方法数？
容斥原理
集合的并
设 $U$ 中元素有 $n$ 种不同的属性，第 $i$ 种属性称为 $P$ ，拥有属性 $P$ 的元素构成集合 $S$ ，那么$\begin{aligned}
\left|\bigcup_{i=1}^{n} S_{i}\right|= & \sum_{i}\left|S_{i}\right|-\sum_{i<j}\left|S_{i} \cap S_{j}\right|+\sum_{i<j<k}\left|S_{i} \cap S_{j} \cap S_{k}\right|-\cdots
+(-1)^{m-1} \sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_i}\right|+\cdots+(-1)^{n-1}\left|S_{1} \cap \cdots \cap S_{n}\right|
\end{aligned}$
即：$\begin{aligned}
\left|\bigcup_{i=1}^{n} S_{i}\right|= \sum^n_{m-1} (-1)^{m-1} \sum_{a_i<a_{i+1}}\left| \bigcap_{i=1}^{m} S_{a_i}\right|
\end{aligned}$
集合的并等于集合的交的交错和（奇正偶负）
使用的二进制位来表示每个集合**选（1）与不选（0）**的状态
Q：给定一个整数 $n$ 和 $m$ 个不同的质数 $p _ { 1 } , p _ { 2 } , \cdots , p _ { m }$ ，求 $1\to n$ 中能被 $p _ { 1 } , p _ { 2 } , \cdots , p _ { m }$ 中的至少一个数整除的数有多少个？其中$m \leq 16 , n , p _ { i } \leq 10 ^ { 9 }$
A：交集的大小等于 $n$ 除以质数的乘积。
$| S _ { 1 } | = \frac { n } { p _ { 1 } }$ ，$ | S _ { 1 } \cap S _ { 2 } | = \frac { n } { p _ { 1 } + p _ { 2 } } $，$ | S _ { 1 } \cap S _ { 2 } \cap S _ { 3 } | = \frac { n } { p _ { 1 }+ { p _ { 2 } + p _ { 3 } } }$
若有 $3$ 个质数，就需要 $3$ 个二进制位来表示所有状态
$001 \rightarrow S _ { 1 }$ ， $010 \rightarrow S _ { 2 }$ ，$100 \rightarrow S _ { 3 }$
$011 \rightarrow S _ { 1 } \cap S _ { 2 }$ ， $101 \rightarrow S _ { 1 } \cap S _ { 3 }$ ， $011 \rightarrow S _ { 2 }\cap S _ { 3 } $
$111 \rightarrow S _ { 1 } \cap S _ { 2 }\cap S_{3}$ ， $000 \rightarrow \varnothing$
我们只要枚举从 $001$ 到 $111$ 的每个状态，就可以计算出全部交集的交错和。
时间复杂度： $O ( m * 2 ^ { m } )$
1 | // 此代码需要针对特定问题研究 |
集合的交
集合的交等于全集减去补集的并，补集的并使用容斥原理求解
即 $\begin{aligned}
\left|\bigcap_{i=1}^{n} S_{i}\right|= \left|U\right|- \left| \bigcup_{i=1}^{m} \overline {S_{i}}\right|
\end{aligned}$
本质还是求集合的并，只是转换了思维；
容斥原理思路
1 | // 此代码需要针对特定问题研究 |
整除分块
单变量整数分块
时间复杂度： $O(\sqrt n)$
- 求 $\sum\limits _ { i = 1 } ^ { n } \lfloor \dfrac { n } { i } \rfloor$ ；
性质1：分块的块数 $≤2\lfloor\sqrt n\rfloor$ 保证时间复杂度
当 $i \le \lfloor\sqrt n\rfloor $ 时，$\lfloor \dfrac{n}{i} \rfloor$ 有 $\sqrt n$ 种取值
当 $i \le \lfloor\sqrt n\rfloor $ 时， $\lfloor \dfrac{n}{i} \rfloor \le \lfloor\sqrt n\rfloor$ ，$\lfloor \dfrac{n}{i} \rfloor$ 至多有 $\lfloor\sqrt n\rfloor$ 种取值；
性质2： $i$ 所在块的右端点为 $\lfloor \dfrac{n}{\lfloor \dfrac{n}{i} \rfloor} \rfloor$ 计算方法
$i$ 所在块的值 $k=\lfloor \dfrac{n}{i} \rfloor$ ，则 $k \le \dfrac{n}{i}$ ，则 $\lfloor \dfrac{n}{k} \rfloor \ge \lfloor \dfrac{n}{\lfloor \dfrac{n}{i} \rfloor} \rfloor=\lfloor i \rfloor =i$ ；
所以 $i_{max}=\lfloor \dfrac{n}{k} \rfloor = \lfloor \dfrac{n}{\lfloor \dfrac{n}{i} \rfloor} \rfloor$ ；
代码实现 r=n/(n/l)
- 求 $\sum\limits _ { i = 1 } ^ { n } f(i)\cdot\lfloor \dfrac { n } { i } \rfloor$ ；
总时间复杂度： $O(n+\sqrt n)$ （前缀和时间复杂度： $O(n)$ 整除分块时间复杂度 $O(\sqrt n)$）
先预处理出 $f(i)$ 的前缀和 $s(i)=\sum\limits ^i_{j=1}f(j)$ ，再枚举每一块 $[l,r]$ ，累加每块的贡献。
1 | // s[]为前缀和 |
双变量整数分块
总时间复杂度： $O(n+\sqrt n)$ （前缀和时间复杂度： $O(n)$ 整除分块时间复杂度 $O(\sqrt n)$）
$ \left\lfloor\dfrac{\lfloor\tfrac{m}{k}\rfloor}{d}\right\rfloor =\left\lfloor\dfrac{m}{k d}\right\rfloor$
- 求 $\sum\limits _ { i = 1 } ^ { n } f(i)\cdot\lfloor \dfrac { n } { i } \rfloor\cdot\lfloor \dfrac { m } { i } \rfloor$ ；（ $n \le m$ ，如果不满足，或许可以交换一下 $n$ 和 $m$ ）
先预处理出 $f(i)$ 的前缀和 $s(i)=\sum \limits ^i_{j=1}f(j)$ ，再枚举每一块 $[l,r]$ ，累加每块的贡献。
因此每次枚举应该取到 $\lfloor \dfrac { n } { l } \rfloor$ 和 $\lfloor \dfrac { m } { l} \rfloor$ 较小的那个一段，乘以对应的 $s(i)$ 进行累加。
1 | // s[]为前缀和 |
生成函数
| 普通生成函数 | 指数生成函数 | |
|---|---|---|
| 定义 | $F ( x ) = \sum a _ { n } x ^ { n }$ | $F ( x ) = \sum a _ { n } \dfrac{x ^ { n }}{n!}$ |
| 卷积 | $\sum \limits _ { i \ge 0 } a _ { i } x ^ { i } \sum \limits _ { j \ge 0 } b _ { j } x ^ { j } = \sum \limits _ { n \ge 0 } x ^ { n } \sum \limits_ { i = 0 } ^ { n } a _ { i } b _ { n - i }$ | $\sum\limits _ { i \ge 0 } a _ { i } \dfrac { x ^ { i } } { i ! } \sum\limits _ { j \ge 0 } b _ { j } \dfrac { x^j }{j!} = \sum\limits _ { n \ge 0 } \dfrac { x ^ { n } }{n!} \sum\limits _ { i = 0 } ^ { n } \dfrac { n ! } { i ! ( n - i ) ! } a _ { i } b _ { n - i }$ |
| 构造 | $( 1 + x ^ { 1 } + \cdots + x ^ { a _ { 1 } } ) \cdots ( 1 + x ^ { 1 } + \cdots + x ^ { a _ { n } } )$ | $( 1 + \dfrac { x ^ { 1 } } { 1 ! } + \dfrac { x ^ { 2 } } { 2 ! } + \cdots + \dfrac { x ^ { a _ { 1 } } } { a _ { 1 } ! } )\cdots ( 1 + \dfrac { x ^ { 1 } } { 1 ! } + \dfrac { x ^ { 2 } } { 2 ! } + \cdots + \dfrac { x ^ { a _ { n } } } { a _ { n} ! } )$ |
| 用途 | 多重集组合数 | 多重集排列数 |
| 结果 | $x^m$ 的系数即组合数 | $\dfrac{x^m}{m!}$ 的系数即排列数 |
普通生成函数
$F ( x ) = \sum _ { n \geq 0 } a _ { n } x ^ { n }$
加减操作（必须数量相同）：
$ \begin{align} F ( x ) \pm G ( x ) &= \sum _ { i \ge 0 } a _ { i } x ^ { i } \pm \sum _ { j \geq 0 } b _ { j } x ^ { j } \ & = \sum _ { n \geq 0 } ( a _ { n } + b _ { n } ) x ^ { n } \end{align} $
乘法操作（卷积）：
$\begin{aligned}
F(x) G(x) & =\sum_{i \geq 0} a_{i} x^{i} \sum_{j \geq 0} b_{j} x^{j} \
& =\sum_{n \geq 0} x^{n} \sum_{i=0}^{n} a_{i} b_{n-i} \quad(\text { 令 } i+j=n)
\end{aligned}$
例如 $n=3$ ，则 $x^3$ 的系数为 $a _ { 0 } b _ { 3 } + a _ { 1 } b _ { 2 } + a _ { 2 } b _ { 1 } + a _ { 3 } b _ { 0 }$
因此 $F(x)G(x)$ 是序列 $\lt \sum _ { i = 0 } ^ { n } a _ { i } b _ { n - i } \gt$ 的普通生成函数。
解决多重集组合数问题
问题：有 $n$ 种物品，每种物品有 $a_i$ 个，问取 $m$ 个物品的组合数？
设从每种物品中取 $b_i$ 个， $0 \le b_i \le a_i$，对于一组选定的 $b_i$ 进行组合的方案数为 $1$。
例如，取 $3$ 个 $A$ 、 $1$ 个 $B$ 的方案就是 ${AAAB}$ ；取 $2$ 个 $A$ 、 $2$ 个 $B$ 的方案就是 ${AABB}$ 。
那么，所有满足 $b_1+b_2+\cdots+b_n=m$ 的方案之和，即答案。
构造普通生成函数
第 $1$ 种物品的生成函数为 $( 1 + x ^ { 1 } + x ^ { 2 } + \cdots + x ^ { a _ { 1 } } )$ ，第 $n$ 种物品的生成函数为 $( 1 + x ^ { 1 } + x ^ { 2 } + \cdots + x ^ { a _ { n } } )$
即求 $x^m$ 的系数。
*注意：指数即物品个数，系数即组合数。*灵活选取指数前面的系数！
问题：有 $n$ 种水果，每种水果选购的个数在 $[a_i,b_i]$ 之间问，买 $m$ 个水果有多少种购买方案？
转化：构造生成函数 $( x ^ { a_1 } + \cdots + x ^ { b _ { 1 } } ) ( x ^ { a _ { 2 } } + \cdots + x ^ { b _ { 2 } } ) \cdots ( x ^ {a _ n } + \cdots + x ^ { b _ { n } })$ ，求 $x^m$ 的系数。
代码模拟括号的展开。
1 | int n, m; // n代表物品种数，m代表最终选取的个数 |
指数生成函数
$F ( x ) = \sum _ {n \ge 0} a _ { n ! } \frac { x ^ { n } } { n ! }$
序列 $<1,1,1,\cdots>$ 的指数生成函数是 $1 + \dfrac { x } { 1 ! } + \dfrac { x ^ { 2 } } { 2 ! } + \dfrac { x ^ { 3 } } { 3 ! } + \cdots = \sum \limits _ { n \geq 0 } ^ { x ^ { n } } = e ^ { x }$
序列 $<1 , p , p ^ { 2 },\cdots >$ 的指数生成函数是 $1 + p \dfrac { x } { 1 ! } + p ^ { 2 } \dfrac { x ^ { 2 } } { 2 ! } + p ^ { 3 } \dfrac { x ^ { 3 } } { 3 ! } + \cdots = \sum _ { n \geq 0 } p ^ { n } \dfrac { x ^ { n } } { n ! } = e ^ { p x }$
加减操作（必须数量相同）：
$\left. \begin{align} F ( x ) \pm G ( x ) &= \sum _ { i \geq 0 } a _ { i } \frac { x ^ { i } } { i! } \pm \sum _ { j \geq 0 } b _ { j } \frac { x ^ { j } } { j ! } \ &= \sum _ { n \geq 0 } ( a _ { n } + b _ { n } ) \frac { x ^ { n } } { n ! } \end{align} \right.$
因此 $F(x)±G(x)$ 是序列 $<a_n±b_n>$ 的指数生成函数。
$ \begin{align} F ( x ) G ( x ) & = \sum \limits_ { i \ge 0 } a _ { i } \dfrac { x ^ { i } }{i!} \sum \limits _ { j \geq 0 } b _ { j } \dfrac { x ^ { j } } { j ! } \&= \sum _ { n \ge 0 } x ^ { n } \sum _ { i = 0 } ^ { n } a _ { i } b _ { n - i } \dfrac { 1 } { i ! ( n - i ) ! } \&= \sum _ { n = 0 } \frac { x ^ { n } } { n ! } \sum _ { i = 0 } ^ { n } \frac { n ! } { i ! ( n - i ) ! } a _ { i } b _ { n - i } \&= \sum _ { n \geq 0 } \frac { x ^ { n } } { n ! } \sum _ { i = 0 } ^ { n } C _ { n } ^ { i } a _ { i } b _ { n - i }\end{align} $
因此 $F(x)G(x)$ 是序列 $\lt \sum _ { i = 0 } ^ { n } C _ { n } ^ { i } a _ { i } b _ { n - i } \gt$ 的指数生成函数。
解决多重集排列数问题
问题：有 $n$ 种物品，每种物品有 $a_i$ 个，问取 $m$ 个物品的排列数？
设从每种物品中取 $b _ { i }$ 个，$0 \leq b _ { i } \leq a _ { i }$ ，$m = \sum _ { i = 1 } ^ { n } b _ { i }$ ， 对于一组选定的 $b _ { i }$ 进行排列的方案数为 $\dfrac { m ! } { b _ { 1} !b _ { 2 }! \cdots b _ { n } !}$
若 $m$ 个物品互不相同，其排列数为 $m!$ ，分母就是对每种相同物品的排列数去重。
例如
取 $3$ 个 $A$ 、 $1$ 个 $B$ 的排列数为 $\dfrac { 4 ! } { 3 ! 1 ! } = \dfrac { 24 } { 6 } = 4$ ，即 $<!–swig28–>{i^{x}} \sum_{j=1}^{\infty} \frac{b_{j}}{j^{x}} \
= & \left(\frac{a_{1}}{1^{x}}+\frac{a_{2}}{2^{x}}+\frac{a_{3}}{3^{x}}+\frac{a_{4}}{4^{x}}+\cdots\right)\left(\frac{b_{1}}{1^{x}}+\frac{b_{2}}{2^{x}}+\frac{b_{3}}{3^{x}}+\frac{b_{4}}{4^{x}}+\cdots\right) \
= & \frac{a_{1} b_{1}}{1^{x}}+\frac{a_{1} b_{2}+a_{2} b_{1}}{2^{x}}+\frac{a_{1} b_{3}+a_{3} b_{1}}{3^{x}}+\frac{a_{1} b_{4}+a_{2} b_{2}+a_{4} b_{1}}{4^{x}}+\cdots \
= & \sum_{n=1}^{\infty} \frac{1}{n^{x}} \sum_{d \mid n} a_{d} \frac{b_{n}}{d}
\end{aligned}$
$\dfrac{1}{6^x} $ 的系数 $a _ { 1 } b _ { 6 } + a _ { 2 } b _ { 3 } + a _ { 3 } b _ { 2 } + a _ { 6 } b _ { 1 }$ （枚举 $6$ 的约数）
欧拉函数
$\varphi ( n ) = \sum\limits _ { i = 1 } ^ { n } [ \gcd ( i , n ) = 1 ]$
性质： $\sum\limits _ { d | n } \varphi ( d ) = n$
莫比乌斯函数
$\begin{align*}\begin{split}\mu(n)= \left {\begin{array}{lr}1,& n=1\0,& n含相同质因子\(-1)^s,& s为n的不同质因子的个数\end{array}\right.\end{split}\end{align*}$
性质： $\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]$
证明： $n=1$ 时， $d=1$ ， $\mu(1)=1$
当 $n>1$ 时， $n = p _ { 1 } ^ { \alpha _ { 1 } } p _ { 2 } ^ { \alpha _ { 2 } } \cdots p _ { s } ^ { \alpha _ { s } }$ ，令 $n ^ { \prime } = p _ { 1 } p _ { 2 } \cdots p _ { s }$
$\sum \limits _ { d |n } \mu ( d ) = \sum \limits _ { d | n ^ { \prime } } \mu ( d )$ ，因为质因子重复会导致 $\mu(d)$ 为 $0$ 。
约数由质因子或乘积构成，根据容斥原理
不取任何质因子的方案数： $C_s^0$
取 $1$ 个质因子的方案数：$C_s^1$
取 $2$ 个质因子的方案数：$C_s^2$
$\dots$
$\begin{aligned}\sum \limits _ { d |n } \mu ( d ) &= \sum \limits _ { d | n ^ { \prime } } \mu ( d )\&= C^0_s + ( - 1 ) C^1_s + ( - 1 ) ^ { 2 } C^2_s + \cdots + ( - 1 ) ^ { s } C^s_s \&=(1+(-1))^{s} \ &=0\end{aligned} $
欧拉函数和莫比乌斯函数的联系：$\sum \limits _ { d | n } \mu ( d ) \dfrac { n } { d } = \varphi ( n )$
证明： $n=1$ 时， $d=1$ ， $\mu(1)=\varphi(1)=1$
当 $n>1$ 时， $n = p _ { 1 } ^ { \alpha _ { 1 } } p _ { 2 } ^ { \alpha _ { 2 } } \cdots p _ { s } ^ { \alpha _ { s } }$ ，令 $n ^ { \prime } = p _ { 1 } p _ { 2 } \cdots p _ { s }$
$\sum \limits _ { d |n } \mu ( d ) \dfrac{n}{d}= n\sum \limits _ { d | n ^ { \prime } }\dfrac{ \mu ( d )}{d}$ ，因为质因子重复会导致 $\mu(d)$ 为 $0$ 。
$\begin{align}\sum \limits _ { d |n } \mu ( d ) \dfrac{n}{d}&= n\sum \limits _ { d | n ^ { \prime } }\dfrac{ \mu ( d )}{d} \
& = n\left(1-\left(\frac{1}{p_{1}}+\cdots+\frac{1}{p_{s}}\right)+\left(\frac{1}{p_{1} p_{2}}+\cdots+\frac{1}{p_{s-1} p_{s}}\right)-\cdots\right) \ & = n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right) \cdots\left(1-\frac{1}{p_{s}}\right) \ & = \varphi(n)
\end{align}$
狄利克雷卷积
定义： $f ( n ) $ ， $ g ( n )$ 是两个积性函数，
$( f * g ) ( n ) = \sum \limits_ { d | _ { n } } f ( d ) g ( \dfrac { n } { d } ) = \sum\limits _ { d | n } f ( \dfrac { n } { d } ) g ( d )$
规律：
- 交换律： $fg=gf$
- 结合律： $(fg)h=f(gh)$
- 分配律： $(f+g)h=fh+g*h$
三个常用函数：
- 元函数： $\varepsilon ( n ) = [ n = 1 ]$
- 常数函数： $1(n)=1$
- 恒等函数： $id(n)=x$
常用函数：
- $\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]\Leftrightarrow \mu*1=\varepsilon$
- $\sum\limits _ { d | n } \varphi ( d ) = n \Leftrightarrow \varphi*1=id$
- $\sum \limits _ { d | n } \mu ( d ) \dfrac { n } { d } = \varphi ( n ) \Leftrightarrow \mu*id=\varphi$
- $f*\varepsilon=f$
- $f*1\neq f$
和式的变换
和式的变换规则
- 分配律： $\sum \limits _ { k \in K } c a _ { k } = c \sum\limits _ { k \in K } a _ { k }$
- 结合律： $\sum \limits _ { k \in K } ( a _ { k } + b _ { k } ) = \sum \limits _ { k \in K } a _ { k } + \sum \limits _ { k \in K } b _ { k }$
- 交换律： $\sum \limits _ { k \in K } a _ { k } = \sum\limits _ { p(k) \in K } a _ { p(k) }$ ， $p(k)$ 为指标集的任何一个排列
和式的变换技术
- 替换条件式
$d|gcd(i,j)=[d|i][d|j]$
$\sum_\limits{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d | \operatorname{gcd}(i, j)} d=\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d=1}^{n}[d| i][d | j] d$ ，第二个式子内部 $\sum\limits_{d=1}^{n}[d|i][d |j] d$ ，上面的 $n$ 可以取任何大于的数 $\min(n,m)$
- 替换指标变量
$\begin{align}\sum \limits_ { i = 1 } ^ { n } \sum \limits_ { j = 1 } ^ { m } [ g c d ( i , j ) = k ]&=\sum \limits_ { ik = 1 } ^ { n } \sum \limits_ { jk = 1 } ^ { m } [ g c d ( ik , jk ) = k ]\&=\sum \limits_ { ik = 1 } ^ { n } \sum \limits_ { jk = 1 } ^ { m } [ g c d ( i , j ) = 1\&=\sum \limits_ { i = 1 } ^ { \lfloor\dfrac{n}{k} \rfloor} \sum \limits_ { j = 1 } ^ { \lfloor\dfrac{m}{k} \rfloor } [ g c d ( i , j ) = 1 ]\end{align}$
注意：最后一步的下标从 $1$ 开始的原因是，因为上一步的枚举是从 $1$ 开始的。
- 交换求和次序
$\sum \limits_ { i = 1 } ^ { n } \sum \limits_ { j = 1 } ^ { m } A ( i ) B ( j ) = \sum \limits_ { j = 1 } ^ { m } \sum \limits_ { j = 1 } ^ { n } A ( i ) B ( j )$
- 分离变量
$\sum \limits_ { i = 1 } ^ { n } \sum \limits_ { j = 1 } ^ { m } A ( i ) B ( j ) = \sum \limits_ { j = 1 } ^ { m }A(i) \sum \limits_ { j = 1 } ^ { n } B ( j )$
和式的变换技巧
- 莫比乌斯函数的性质
$\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]\Longleftrightarrow [ \gcd(i,j) = 1 ]=\sum\limits _ { d | \gcd(i,j) } \mu( d ) $
- 整除性质
$\sum \limits_ { i=1 } ^ { n } [d|i]=\lfloor \dfrac{n}{d}\rfloor$ ，容易转化为整除分块求 $\sum\limits _ { i = 1 } ^ { n } f(i)\cdot\lfloor \dfrac { n } { i } \rfloor$
- 求 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m}[\gcd(i,j)=k]$
$\sum _ \limits{ i = 1 } ^ { n } \sum \limits_ { j = 1 } ^ { m } [ g c d ( i , j ) = k ]=\sum_\limits{d=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \mu(d)\left\lfloor\dfrac{n}{k d}\right\rfloor\left\lfloor\dfrac{m}{k d}\right\rfloor$ （ $n<m$ ）
证明：
当 $k=1$ 时，
$ \begin{align}&\sum_{i = 1}^{n} \sum_{j = 1}^{m}[\operatorname{gcd}(i, j) = 1]
\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{d \mid \operatorname{gcd}(i, j)} \mu(d)
\ = &\sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{d = 1}^{n}[d \mid i][d \mid j] \mu(d)
\ = &\sum_{d = 1}^{n} \mu(d) \sum_{i = 1}^{n}[d \mid i] \sum_{j = 1}^{m}[d \mid j]
\ = &\sum_{d = 1}^{n} \mu(d)\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{align}$
当 $k\neq 1$ 时，
$ \begin{align}&\sum_{i = 1}^{n} \sum_{j = 1}^{m}[\operatorname{gcd}(i, j) = k] \ = & \sum \limits_ { i = 1 } ^ { \lfloor\dfrac{n}{k} \rfloor} \sum \limits_ { j = 1 } ^ { \lfloor\dfrac{m}{k} \rfloor } [ g c d ( i , j ) = 1 ]\end{align} $
其实到这一步，已经转化为 $k=1$ 的情况了，只不过 $n$ 需要替换为 $\lfloor\dfrac{n}{k}\rfloor$ ， $m$ 需要替换为 $\lfloor\dfrac{m}{k}\rfloor$ 。
即结果可以得到 $\sum \limits_{d = 1}^{\lfloor\tfrac{n}{k}\rfloor} \mu(d)\left\lfloor\dfrac{\lfloor\tfrac{n}{k}\rfloor}{d}\right\rfloor\left\lfloor\dfrac{\lfloor\tfrac{m}{k}\rfloor}{d}\right\rfloor= \sum\limits_{d = 1}^{\lfloor\tfrac{n}{k} \rfloor} \mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor $ （$ \left\lfloor\dfrac{\lfloor\tfrac{m}{k}\rfloor}{d}\right\rfloor =\left\lfloor\dfrac{m}{k d}\right\rfloor$ ）
继续往下写：
$\begin{align}\ = & \sum_{i = 1}^{\lfloor\tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor\tfrac{m}{k} \rfloor} \sum_{d | \operatorname{gcd}(i, j)} \mu(d)
\ = &\sum_{i = 1}^{\lfloor\tfrac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor\tfrac{m}{k} \rfloor} \sum_{d = 1}^{\lfloor\tfrac{n}{k} \rfloor}[d | i][d | j] \mu(d)
\ = &\sum_{d = 1}^{\lfloor\tfrac{n}{k} \rfloor} \mu(d) \sum_{i = 1}^{\lfloor\tfrac{n}{k} \rfloor}[d| i] \sum_{j = 1}^{\lfloor\tfrac{m}{k} \rfloor}[d |j]
\ = &\sum_{d = 1}^{\lfloor\tfrac{n}{k} \rfloor} \mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor \end{align}$
然后利用双变量整数分块求结果。
- 求 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m}[\gcd(i,j)\in \text{prim}]$
$\begin{align}
&\sum_{i=1}^{n} \sum_{j=1}^{m}[\operatorname{gcd}(i, j) \in \text {prim}] \
=&\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{n}[\operatorname{gcd}(i, j)=k][k \in \text {prim}] \
=&\sum_{k=1}^{n} \sum_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \sum_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor}[\operatorname{gcd}(i, j)=1][k \in \text {prim}] \
=&\sum_{k=1}^{n} \sum_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \sum_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor} \sum_{d \mid \operatorname{gcd}(i, j)} \mu(d)[k \in \text {prim}] \
=&\sum_{k=1}^{n} \sum_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \sum_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor} \sum_{d=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor}[d | i][d | j] \mu(d)[k \in \text {prim}] \
=&\sum_{k=1}^{n} \sum_{d=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \mu(d) \sum_{i=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor}[d|i] \sum_{j=1}^{\left\lfloor\tfrac{m}{k}\right\rfloor}[d | j][k \in \text {prim}] \=&\sum\limits_{k=1}^n\sum\limits_{d=1}^{\lfloor\tfrac{n}{k}\rfloor}\mu(d)\lfloor\dfrac{n}{kd}\rfloor\lfloor\dfrac{m}{kd}\rfloor[k \in \text{prim}]\end{align}$
因为分母有 $k,d$ 两个变量，所以此时还无法使用整除分块，可以整体代换让他可以使用整除分块。
令 $T=kd$ ，则 $d=\dfrac{T}{k}$ ，代换 $d$ 的原因，是因为原式中有 $\lfloor \dfrac{n}{k} \rfloor$ ，这样代换可以消去 $k$ 。
$\begin{align}
=&\sum_{k=1}^{n} \sum_{\tfrac{T}{k}=1}^{\left\lfloor\tfrac{n}{k}\right\rfloor} \mu\left(\frac{T}{k}\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor[k \in \text {prim}] \
=&\sum_{k=1}^{n} \sum_{T=1}^{n} \mu\left(\frac{T}{k}\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor[k \in \text {prim}] \
=&\sum_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \sum_{k=1}^{n} \mu\left(\frac{T}{k}\right)[k \in \text {prim}] \
=&\sum_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \sum_{k \in \text {prim}} \mu\left(\frac{T}{k}\right)\=&\sum_{T=1}^{n}\sum_{k \in \text {prim}} \mu\left(\frac{T}{k}\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor
\end{align}$
然后先预处理 $s(x)=\sum\limits_{k \in \text {prim}} \mu\left(\dfrac{T}{k}\right)$ ，使用双变量整除分块即可。
大致时间复杂度： $n(\dfrac{1}{2}+\dfrac{1}{3}+\cdots)\approx O(n\ln\ln n)$
- 求$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m}d(ij)$， $d(x)$ 为约数个数。
结论： $d(ij)=\sum\limits_{x|i} \sum\limits_{y|j}[\gcd(x,y)=1]$
$\begin{aligned}
& \sum_{i=1}^{n} \sum_{j=1}^{m} d(i j) \
= & \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{x \mid i} \sum_{y \mid j}[\operatorname{gcd}(x, y)=1] \
= & \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{x=1}^{n} \sum_{y=1}^{m}[x |i][y | j][\operatorname{gcd}(x, y)=1] \
= & \sum_{x=1}^{n} \sum_{y=1}^{m} \sum_{i=1}^{n}[x | i] \sum_{j=1}^{m}[y | j][\operatorname{gcd}(x, y)=1] \
= & \sum_{x=1}^{n} \sum_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y}\rfloor[\operatorname{gcd}(x, y)=1] \
= & \sum_{x=1}^{n} \sum_{y=1}^{m} \rfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y}\rfloor \sum_{d=1}^{n}[d |x][d|y] \mu(d) \
= & \sum_{d=1}^{n} \mu(d) \sum_{x=1}^{n}\lfloor\frac{n}{x}\rfloor[d | x] \sum_{y=1}^{m} \lfloor \frac{m}{y}\rfloor[d | y]
\end{aligned}$
因为： $\sum\limits_{d=1}^{n}\sum\limits_{x=1}^{n}\lfloor \dfrac{n}{x}\rfloor[d|x]=\sum\limits_{d=1}^{n}\sum\limits_{dx=1}^{n}\lfloor\dfrac{n}{dx}\rfloor$
即将 $x \rightarrow dx,y \rightarrow dy$
$\begin{aligned}&=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{dx=1}^{n}\lfloor\dfrac{n}{dx}\rfloor\sum\limits_{dy=1}^{m}\lfloor\dfrac{m}{dy}\rfloor\&=\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{x=1}^{\lfloor \tfrac{n}{d}\rfloor}\lfloor\dfrac{n}{dx}\rfloor\sum\limits_{y=1}^{\lfloor \tfrac{m}{d}\rfloor}\lfloor\dfrac{m}{dy}\rfloor\end{aligned}$
令 $F ( n ) = \sum \limits_ { i = 1 } ^ { n } \lfloor\dfrac { n } { l } \rfloor$
$=\sum\limits_{d=1}^{n}\mu(d)F(\lfloor\dfrac{n}{d}\rfloor)F(\lfloor\dfrac{m}{d}\rfloor)$
预处理 $\mu(d)$ 前缀和，复杂度为 $O(n)$
对于每个 $n$ 利用单变量整数分块求 $F(n)$ ，复杂度为 $O(n\sqrt n)$
查询结果利用双变量整数分块，复杂度为为 $O(\sqrt n)$
- 求 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m}f(\gcd(i,j))$
莫比乌斯反演
$f ( n ) = \sum \limits_ { d | n } g ( d ) \Leftrightarrow g ( n ) = \sum \limits_ { d |n } \mu ( d ) f ( \dfrac { n } { d } )$
$f(n),g(n)$ 均为积性函数
$f(n) \xLeftrightarrow[g为f的莫比乌斯逆变换]{f为g的莫比乌斯变换} g(n)$
证明1：
若 $f=g1$ ，则 $\muf=\mug1=g*\mu1=g\varepsilon=g$
若 $g=\muf$ ，则 $g1=\muf1=f*\mu1=f\varepsilon=f$
证明2：
三个常用函数：
- 元函数： $\varepsilon ( n ) = [ n = 1 ]$
- 常数函数： $1(n)=1$
- 恒等函数： $id(n)=x$
常用函数：
1. $\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]\Leftrightarrow \mu*1=\varepsilon$
- $\sum\limits _ { d | n } \varphi ( d ) = n \Leftrightarrow \varphi*1=id$
- $\sum \limits _ { d | n } \mu ( d ) \dfrac { n } { d } = \varphi ( n ) \Leftrightarrow \mu*id=\varphi$
- $f*\varepsilon=f$
- $f*1\neq f$
$\begin{align}
\sum_{d \mid n} \mu(d) f\left(\dfrac{n}{d}\right) & = \sum_{d \mid n} \mu(d) \sum_{k \mid \tfrac{n}{d}} g(k) \ & = \sum_{d \mid n} \sum_{k \mid \tfrac{n}{d}} \mu(d) g(k)\ & = \sum_{k \mid n} \sum_{d \mid \tfrac{n}{k}} \mu(d) g(k) \ & = \sum_{k \mid n} g(k) \sum_{d \mid \tfrac{n}{k}} \mu(d) \& = g(n)
\end{align}$
重点在于第2，3行之间的交换 $k$ 和 $d$ ，因为 $n$ 是固定，若 $k,d$ 一方为 $n$ 的因子，另一方就是枚举这一方的因子，本质是一样的，所以可以交换位置。
杜教筛
时间复杂度： $O(n^{\tfrac{2}{3}})$
时间复杂度的证明：杜教筛
求 $s ( n ) = \sum \limits_ { i = 1 } ^ { n } f ( i )$ ， $f$ 为积性函数
构造极性函数 $g$ ，使得 $f*g$ 的前缀和容易计算
根据递推式： $g ( 1 ) s ( n ) = \sum \limits _ { i = 1 } ^ { n } ( f * g ) ( i ) - \sum \limits _ { i = 2 } ^ { n } g ( i ) s ( \dfrac { n } { i } )$
递归计算 $s(n)$ 。
优化
- 使用线性筛预处理 $n$ 较小时的 $s(n)$ 来剪枝
- 使用哈希表做记忆化剪枝
- 使用整除分块做递归
递推式证明
狄利克雷卷积：
$( f * g ) ( n ) = \sum \limits_ { d | _ { n } } f ( d ) g ( \dfrac { n } { d } ) = \sum\limits _ { d | n } f ( \dfrac { n } { d } ) g ( d )$
证明：
$\begin{array}{l}
\sum\limits_{i=1}^{n}(f * g)(i) \
=\sum\limits_{i=1}^{n} \sum\limits_{d \mid i} f\left(\frac{i}{d}\right) g(d)=\sum\limits_{i=1}^{n} \sum\limits_{d=1}^{n}[d \mid i] f\left(\frac{i}{d}\right) g(d) \
=\sum\limits_{d=1}^{n} \sum\limits_{i=1}^{n}[d \mid i] f\left(\frac{i}{d}\right) g(d)=\sum\limits_{d=1}^{n} \sum\limits_{i d=1}^{n}[d | i d] f\left(\tfrac{i d}{d}\right) g(d) \
=\sum\limits_{d=1}^{n} \sum\limits_{i=1}^{\lfloor \tfrac{n }{ d}\rfloor} f(i) g(d)=\sum\limits_{d=1}^{n} g(d) s\left(\dfrac{n}{d}\right) \
=g(1) s(n)+\sum\limits_{d=2}^{n} g(d) s\left(\dfrac{n}{d}\right)\cdots\cdots分离第一项
\end{array}$
技巧
三个常用函数：
- 元函数： $\varepsilon ( n ) = [ n = 1 ]$
- 常数函数： $1(n)=1$
- 恒等函数： $id(n)=x$
常用函数：
- $\sum\limits _ { d | n } \mu( d ) = [ n = 1 ]\Leftrightarrow \mu*1=\varepsilon$
- $\sum\limits _ { d | n } \varphi ( d ) = n \Leftrightarrow \varphi*1=id$
- $\sum \limits _ { d | n } \mu ( d ) \dfrac { n } { d } = \varphi ( n ) \Leftrightarrow \mu*id=\varphi$
求 $s(n)=\sum\limits^n_{i=1}\varphi(i)$
因为 $\varphi1=id$ ，则 $f=\varphi$ ，$g=1$ ， $fg=id$
$\begin{align}s(n)&=\sum\limits^n_{i=1}id(i)-\sum\limits^n_{i=2}1(i)s(\dfrac{n}{i})\&=\sum\limits^n_{i=1}i-\sum\limits^n_{i=2}s(\dfrac{n}{i})\&=\dfrac{n(n+1)}{2}-\sum\limits^n_{i=2}s(\dfrac{n}{i})\end{align}$
最后对 $s(\dfrac{n}{i})=s(\lfloor\dfrac{n}{i}\rfloor)$ 用哈希表存，再做分块做递归处理即可。
求 $s(n)=\sum\limits^n_{i=1}\mu(i)$
因为 $\mu1=\varepsilon$ ，则 $f=\mu$ ，$g=1$ ， $fg=\varepsilon$
$s(n)=\sum\limits^n_{i=1}\varepsilon(i)-\sum\limits^n_{i=2}1(i)s(\dfrac{n}{i})=1-\sum\limits^n_{i=2}s(\dfrac{n}{i})$
最后对 $s(\dfrac{n}{i})=s(\lfloor\dfrac{n}{i}\rfloor)$ 用哈希表存，再做分块做递归处理即可。
代码
1 | // N取约n^{2/3}，预处理n的三分之二次方 |
命名空间
采用模板设计模式，将杜教筛的部分提取到父类 DJSeive 中，这部分是不需要变的。提供三个接口（虚函数），需要子类实现。gsum 是求 $g$ 的区间和，hsum 是求 $h$ 得前缀和，precal 是预计算部分。
该实现可以实现同时求多个前缀和。使用模板元编程让返回类型当只求一个时，采用 int64_t 类型，当求多个时，采用 array<int64_t, N> 类型。
重载了 array<T, N> 的一些操作，让 array 的操作和普通数保持一致。
模板为洛谷P4213，求 $\mu$ 和 $\varphi$ 的前缀和。要求其他函数，只需修改子类中对应 gsum，hsum ，precal。
1 | // https://www.luogu.com.cn/problem/P4213 |
快速傅里叶变换(FFT)
复数
定义： $z=x+iy$ ，其中 $i^2=-1$
加法： $z_1+z_2=(x_1+x_2)+i(y_1+y_2)$
减法： $z_1-z_2=(x1-x2)+i(y_1-y_2)$
乘法： $z_1*z_2=(x_1x_2-y_1y_2)+i(x_1y_2+x_2y_1)$
单位圆/单位根
单位圆是指复平面上圆心在原点且半径为 $1$ 的圆
圆上的点： $z=\cos\theta+i\sin\theta,(0\le\theta<2\pi)$
把圆 $n$ 等分，可得方程 $z^n=1$ 的 $n$ 个复数解，即单位根
单位根
下面的 $\omega^k_n$ 上标代表第 $k$ 个单位根，不是次方
$\large \omega^k_n=\cos\dfrac{2\pi k}{n}+i\sin \dfrac{2\pi k}{n},(0\le k<n)$
$\large \omega^k_n\omega^m_n=\omega^{k+m}_n,(\omega^k_n)^m=\omega^{km}_n$
FFT基础
FFT要求单位根等分单位圆 $\large n=2^{b\in N}$
性质：
- 周期性 $\large \omega^{k+m}_n=\omega^k_n$
- 对称性 $\large \omega^{k+\tfrac{n}{2}}=-\omega^k_n$
- 折半性 $\large \omega^{2k}n=\omega^k{\tfrac{n}{2}}$
由系数求点值（正变换）
设 $A(x)$ 的系数为 $(a_0,a_1,a_2,\cdots,a_{n-1})$
$\begin{align}A(x)&=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{n-1}x^{n-1}\&=()\cdots\cdots偶数项\&+(a_1+a_3x^2+\cdots+a_{n-1}x^{n-2})x\cdots\cdots奇数项\end{align}$
令$A_1(x)=a_0+a_2x+\cdots+a_{n-2}x^{\tfrac{n}{2}-1}$
令$A_2(x)=a_1+a_3x+\cdots+a_{n-1}x^{\tfrac{n}{2}-1}$
则 $A(x)=A_1(x^2)+A_2(x^2)x$
前半圈：
将 $\large\omega^k_n,(k<\frac{n}{2})$ 带入得
$A(\omega^k_n)=A_1(\omega^{2k}_n)+A_2(\omega^{2k}_n)\omega^{2k}_n$
后半圈：
将 $\large\omega^{k+\tfrac{n}{2}}_n,(k<\frac{n}{2})$ 带入得
$A(\omega^k_n)=A_1(\omega^{2k}_n)+A_2(\omega^{2k}_n)\omega^{2k}_n$
