初等数论（Ⅳ）：狄利克雷卷积和各类反演
bloodstalk
·
·
个人记录
前置知识
积性函数
满足 f(1)=1，并且当 \gcd(a,b)=1 时，有 f(ab) = f(a)f(b)，则称 f(n) 为积性函数。
如果对于全部的 a,b，都有 f(ab)=f(a)f(b)，则称 f(n) 是完全积性函数。
常见积性函数
-
常数函数：1(x)=1（完全积性）
-
恒等函数 id_k(n)=n^k,id_1(n) 简记为 id(n) = n
-
元函数：\varepsilon(n) = [n=1]
-
欧拉函数：\varphi(n)
-
因子函数：d(n)=\prod_1^k(a_i+1),a_i是质因数分解后质因子 p_i 的幂次。
-
除数函数：\sigma(n)=\sum_{d|n}d
-
莫比乌斯函数：
\mu(n) = \left\{
\begin{aligned}
&1,\ \ \ \ \ \ \ \ n=1\\
&(-1)^s,n=p_1p_2\dots p_s\\
&0,\ \ \ \ \ \ \ \ n\text{包含相同质因子}
\end{aligned}
\right.
两个积性函数的性质
欧拉函数
定义
用一个式子表达就是
\varphi(n) = \sum_{i=1}^n[\gcd(i,n)=1]
性质
\sum_{d|n}\varphi(d)=n
证明在我这篇博客里有。
莫比乌斯函数
定义
\mu(n) = \left\{
\begin{aligned}
&1,\ \ \ \ \ \ \ \ n=1\\
&(-1)^s,n=p_1p_2\dots p_s\\
&0,\ \ \ \ \ \ \ \ n\text{包含相同质因子}
\end{aligned}
\right.
性质
\sum_{d|n}\mu(d) = [n=1]
也就是说除了 n=1 的时候这个式子是 1 ,其余的都是 0。
证明：
当 n=1 时， \mu(1) = 1
当 n>1 时，将 n 质因数分解得到 n=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}，令 n'=p_1p_2\dots p_n，那么有
\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)
因为如果有幂次 >2 的因数函数值是 0，所以可以直接舍掉了。
剩下的就直接运用容斥原理解决。
不取任何质因子的方案数为 C_s^0
取一个任何质因子的方案数为 C_s^1
取两个任何质因子的方案数为 C_s^2,\dots
所以最后的答案
= (-1)^0C_s^0+(-1)C_s^1+(-1)^2C_s^2+\dots+(-1)^sC_s^s
=(1+(-1))^s = 0
这个性质往往是逆用的，比如给你一个 [x=k]，我们就可以把它转化成 \displaystyle \sum_{d|\lfloor \frac{x}{k}\rfloor}\mu(d)。
两个函数的联系
\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n)
证明：
$n>1$ 时，$n=p_1^{a_1}p_2^{a_2}\dots p_s^{a_s}$，令 $n'=p_1p_2\dots p_n$，那么有
$$
\sum_{d|n}\mu(d)\frac{n}{d}=n\sum_{d|n}\frac{\mu(d)}{d}=n\sum_{d|n'}\frac{\mu(d)}{d}
$$
这其中 $\mu(d)$ 决定着符号，根据容斥原理，原式
$$
\begin{aligned}
&=n\Bigg(1-\Bigg(\frac{1}{p_1}+\dots+\frac{1}{p_s}\Bigg)+\Bigg(\frac{1}{p_1p_2}+\dots+\frac{1}{p_{s-1}p_s}\Bigg)-\dots\Bigg)\\
&=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_s})\\
&= \varphi(n)
\end{aligned}
$$
其中最后这一步的证明在[这](https://www.luogu.com.cn/paste/49sajxpo)。
## 和式的变换
学会和式的变换有助于我们更好地推式子。
### 和式的变换规则
1. 分配律
$$
\sum_{k\in K}ca_k = c\sum_{k\in K} a_k
$$
2. 结合律
$$
\sum_{k\in K}(a_k+b_k) = \sum_{k\in K}a_k + \sum_{k\in K} b_k
$$
3. 交换律
$$
\sum_{k\in K}a_k = \sum_{p(k)\in K}a_{p(k)}
$$
$p_k$ 指的是标集的任意一个排列
例如，$a_1+a_2+a_3+a_6=a_6+a_2+a_3+a_1
和式的变换魔术
- 替换条件式
- 替换指标变量
\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] = \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1]
- 交换求和次序
\sum_{i=1}^n\sum_{j=1}^mA(i)B(j)=\sum_{j=1}^m\sum_{i=1}^nA(i)B(j)
- 分离变量
\sum_{i=1}^n\sum_{j=1}^mA(i)B(j)=\sum_{i=1}^nA(i)\sum_{j=1}^mB(j)
狄利克雷卷积
定义
$$
(f * g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})=\sum_{n|d}f(\frac{n}{d})g(d)
$$
比如 $(f * g)(4) = f(1)g(4) + f(2)g(2) + f(4)g(1)
性质
-
交换律：f * g = g* f
-
结合律：(f * g) * h = f * (g * h)
-
分配律：(f+g) * h = f * h + g * h
常用卷积关系
-
\sum_{d|n}\mu(d)=[n=1] \Leftrightarrow \mu * 1 = \varepsilon
证明：
(\mu * 1)(n) = \sum_{d|n}\mu(d)1(\frac{n}{d}) = \sum_{d|n}\mu(d) = [n=1] = \varepsilon(n)
-
\sum_{d|n}\varphi(d)=n \Leftrightarrow \varphi * 1 = id
证明：
(\varphi * 1)(n) = \sum_{d|n}\varphi(d)1(\frac{n}{d}) = \sum_{d|n}\varphi(d) = n = id(n)
-
\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n) \Leftrightarrow \mu * id = \varphi
证明：
(\mu * id)(n) = \sum_{d|n}\mu(d)id(\frac{n}{d}) = \sum_{d|n}\mu(d)\frac{n}{d} = \varphi(n)
-
f * \varepsilon = f
证明：
(f * \varepsilon)(n) = \sum_{d|n}f(d)\varepsilon(\frac{n}{d}) = \sum_{d|n}f(d)[\frac{n}{d}=1] = f(n)
这说明 \varepsilon 是狄利克雷卷积的单位元。
莫比乌斯反演
定义
若 f(n),g(n) 均为积性函数，则有
f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})
上面是枚举因数，下面这种形式是枚举倍数
f(n) = \sum_{n \mid d} g(d) \Leftrightarrow g(n) = \sum_{n \mid d} \mu(\frac{d}{n})f(d)
$g(n)$ 称为 $f(n)$ 的**莫比乌斯逆变换**。
证明：
$\text{Method 1}$（卷积角度）
充分性：
若 $f = g * 1$，则 $\mu * f = \mu * g * 1 = g * \mu * 1 = g * \varepsilon = g
必要性：
若 g = \mu * f，则 g * 1 = \mu * f * 1 = f * \mu * 1 = f * \varepsilon = f
这里只证明充分性，详细的证明可见[这里](https://zhuanlan.zhihu.com/p/107369246#:~:text=Proof%3A%E7%94%B1%E5%AE%9A%E7%90%864%20%E7%9F%A5varphi%20%28n%29%3Dnsum_%20%7Bdmid%20n%7Dfrac%20%7Bmu%20%28d%29%7D%20%7Bd%7D%3Dnsum_,p_k%7Dfrac%20%7Bmu%20%28d%29%7D%20%7Bd%7D%3Dnprod_%20%7Bi%3D1%7D%5Ek%20%281-frac%20%7B1%7D%20%7Bp_i%7D%29.)
充分性：
$$
\begin{aligned}
&\ \ \ \ \ \sum_{d|n}\mu(d)f(\frac{n}{d})\\
&=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}g(k) \ \ (\text{代入充分性的条件}) \\
&=\sum_{d|n}\sum_{k|\frac{n}{d}}\mu(d)g(k)\\
&=\sum_{k|n}\sum_{d|\frac{n}{k}}\mu(d)g(k)\\
&=\sum_{k|n}g(k)\sum_{d|\frac{n}{k}}\mu(d) = g(n)
\end{aligned}
$$
其中第三行到第四行采用的交换和号的方式，可以列一个表格感性证明一下，可以看出先枚举行和先枚举列最终的结果是相同的。
但是好像有关 $[\gcd() = k]$ 的用黄金代换式更简单。
# 欧拉反演
其实也是一类套路。
对于类似 $[\gcd() = k]$ 这一类题，我们常常利用黄金代换，也就是反演的一类把这个式子用莫比乌斯函数表示出来，那么对于 $\gcd(i,j)$ 一类的题，我们就可以类似的用欧拉函数来表示。
莫比乌斯反演运用了 $\mu * 1 = \varepsilon$ 的性质，而欧拉反演运用的就是 $\varphi * 1 = id$ 的性质。
求解下面的式子（默认 $n\leq m$）
$$
\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)
$$
因为欧拉函数具有 $\displaystyle \sum_{d|n}\varphi(d) = n$ 的性质，所以我们把 $\gcd(i,j)$ 看作 $n$，就有
$$
\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\varphi(d)\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n[d|i][d|j]\varphi(d)\\
&=\sum_{d=1}^n\varphi(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\
&=\sum_{d=1}^n\varphi(d)\lfloor \frac{n}{d} \rfloor\lfloor \frac{m}{d} \rfloor
\end{aligned}
$$
$\varphi(d)$ 可以线性预处理，这个式子可以 $O(\sqrt n)$ 整除分块，于是复杂度就降下来了。
----
# 一些常见的变换套路
1. 黄金代换
$$
[\gcd(i,j)=1] = \sum_{d|\gcd(i,j)}\mu(d)
$$
莫比乌斯函数性质的逆运用。
2. 转艾佛森括号
$$
d|\gcd(i,j)\rightarrow [d|i][d|j]
$$
以一式举例
$$
\sum_{d|\gcd(i,j)}\mu(d)=\sum_{d=1}^n[d|i][d|j]\mu(d)
$$
3. 套着求和式外壳的常数
$$
\sum_{i=1}^n[d|i] = \lfloor \frac{n}{d} \rfloor
$$
等号左边的实际意义就是让你求 $1\sim n$ 中 $d$ 的倍数的个数，那显然就是 $\lfloor \frac{n}{d} \rfloor$ 个。
4. 一个我也不知道叫啥的变换
$$
\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor \rightarrow \sum_{k=1}^n\sum_{T=1}^n\mu(\frac{T}{k})\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor
$$
通过设 $T=kd$，来把下取整里面的两个变量转化为只有一个变量，方便我们进行整除分块。
5. 有关 $[\gcd(i,j)=1]$ 的套路（默认 $n\leq m$）
$$
\begin{aligned}
&\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\mu(d)\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n[d|i][d|j]\mu(d)\\
&=\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^m[d|i][d|j]\\
&=\sum_{d=1}^n\mu(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\\
&=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{aligned}
$$
于是可以 $O(n)$ 预处理 $\mu(n)$，后面两项整除分块即可。
通过整理式子，我们将一个 $O(n^2)$ 的式子优化到了 $O(n+\sqrt n)$。
6. 升级版 $5
$$
\begin{aligned}
&\ \ \ \ \ \sum{i=1}^n\sum{j=1}^m[\gcd(i,j)=k]\
&\ \ \ \ \ i,j \ \text{同时除以}\ k\
&=\sum{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum{j=1}^{\lfloor \frac{m}{k}\rfloor}[\gcd(i,j)=1]\
&=\sum{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum{j=1}^{\lfloor \frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d)\
\end{aligned}
后面的就都一样了，注意枚举范围即可。
7. 升级版 $6$
\ \ \ \ \ \sum_{i=1}^n\sum_{j=1}^mij[\gcd(i,j)=k]
- $i,j$ 同时除以 $k$
\begin{aligned}
&=\sum{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum{j=1}^{\lfloor \frac{m}{k}\rfloor}ijk^2[\gcd(i,j)=1]\
&=\sum{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum{j=1}^{\lfloor \frac{m}{k}\rfloor}ijk^2\sum_{d|\gcd(i,j)}\mu(d)\
\end{aligned}
- 你会发现多了一个 $k^2$，这是为什么呢？因为你还要考虑 $i,j$ 的贡献，你同时除以 $k$ 了就要乘上原来应该有的 $k^2$ 的贡献。
8.
一个结论
d(ij) = \sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]
$$
证明思路大致是构造一个双射，一一对应。
二项式反演
应该是运用最广泛的一个反演类型。
为什么叫二项式反演？因为它由二项式定理推过来的，并且式子也比较相似。
前置
首先我们知道二项式定理
(a+b)^n = \sum_{i=0}^n\binom{n}{i}a^{n-i}b^i
我们令 a=1,b=-1，就得到我们的推论式
\sum_{i=0}^n(-1)^i\binom{n}{i} = [n=0]
这里因为 0^0 没有意义，我们给它定义成 0^0 =1，其余的 0^k 都是 0。
二项式反演
先给出式子
f(n) = \sum_{i=0}^n\binom{n}{i}g(i) \Longleftrightarrow g(n) = \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)
简单证明一下，只证明从左边推右边
\begin{aligned}
&\ \ \ \ \ \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)\\
&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}g(j)\\
&=\sum_{i=0}^n\sum_{j=0}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}g(j)\\
&=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{i}\binom{i}{j}g(j)\\
&=\sum_{j=0}^n\sum_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}g(j)\\
&=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}\\
&=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=0}^{n-j}(-1)^{n-j-i}\binom{n-j}{i}\\
&=\sum_{j=0}^n\binom{n}{j}g(j)[n=j]=g(n)
\end{aligned}
其中第三行到第四行是一个和式的变换。你可以把它想象成一个下三角，本来是先行再列枚举，变换后就变成了先列后行。
第六行到第七行就是枚举范围的变化，令 i 变为 i+j，相应的范围也发生变化。然后就套用我们的推论式就可以了。
应用
二项式反演往往可以抽象成两种模型。
恰好 \rightarrow 至多型
设 g(m) 代表恰好满足条件 (=m)，剩下的不满足的方案数，也就是答案。
再设 f(m) 表示至多满足条件 (\leq m) 的方案数。
这种题往往 f(m) 是好求的，我们先求出 f(m)，再反演求 g(m)
f(m)=\sum_{i=0}^m\binom{m}{i}g(i) \Rightarrow g(m) = \sum_{i=0}^m(-1)^{m-i}\binom{m}{i}f(i)
恰好 \rightarrow 至少型
设 g(m) 代表恰好满足条件 (=m) ，剩下的不满足的方案数，也就是答案。
再设 f(m) 表示钦定 m 个元素满足条件 (\leq m)，剩下的随便选的方案数。
同理，这种题往往 f(m) 是好求的，我们先求出 f(m)，再反演求 g(m)
f(m)=\sum_{i=m}^n\binom{i}{m}g(i) \Rightarrow g(m) = \sum_{i=m}^n(-1)^{i-m}\binom{i}{m}f(i)
其中 \displaystyle \binom{i}{m} 我们可以理解为，我们钦定了其中 m 个满足限制，那么对于一个满足了 k \ge m 个限制的方案，它就会被我们算 \binom{k}{m} 次，因此要乘一个系数。
这其实是二项式反演的另一种性质，上界变而不是下界，我们再简单证明一下。
\begin{aligned}
&\ \ \ \ \ \sum_{i=m}^n(-1)^{i-m}\binom{i}{m}f(i)\\
&=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}\sum_{j=i}^n\binom{j}{i}g(j)\\
&=\sum_{i=m}^n\sum_{j=i}^n(-1)^{i-m}\binom{j}{i}\binom{i}{m}g(j)\\
&=\sum_{j=m}^n\sum_{i=m}^j(-1)^{n-i}\binom{j}{m}\binom{j-m}{i-m}g(j)\\
&=\sum_{j=m}^n\binom{j}{m}g(j)\sum_{i=0}^{j-m}(-1)^{i-m}\binom{n-j}{i-j}\\
&=\sum_{j=0}^n\binom{n}{j}g(j)\sum_{i=0}^{n-j}(-1)^i\binom{j-m}{i}\\
&=\sum_{j=m}^n\binom{j}{m}g(j)[j=m]=g(m)
\end{aligned}
例题
这是一个典型的错排问题，但是我们也可以用二项式反演来得出答案。
设 g(n) 表示恰好 n 个装错的方案数，这也是我们想求出的，但是它并不好直接求出。
设 f(n) 代表至多 n 个装错的方案数，这个很好求，答案就是全排列，因为每一种方案都符合要求，并且 f(n) 和 g(i) 有如下关系
f_n = \sum_{i=0}^n\binom{n}{i}g_i
你会发现这符合二项式反演的式子，于是 g(n) 就可以求解了。
\begin{aligned}
g(n) &= \sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i\\
&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}i!\\
&=\sum_{i=0}^n\frac{(-1)^{n-i}n!}{(n-i)!}\\
&=\sum_{i=0}^n\frac{(-1)^{i}n!}{i}\\
\end{aligned}
于是这题就做完了。
总结
二项式反演的题和大多数反演题一样，关键在于找出关系，判断是否符合二项式反演的式子，接着用好表示的来反演出不好表示的，再做化简。
斯特林反演
见组合数学斯特林数部分。
单位根反演
咕咕
子集反演
咕咕