前置知识

积性函数

满足 \(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\) 时，\(\varphi(1)=\mu(1)=1\)；

\(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} \]

其中最后这一步的证明在这。

和式的变换

学会和式的变换有助于我们更好地推式子。

和式的变换规则

分配律

\[ \sum_{k\in K}ca_k = c\sum_{k\in K} a_k \]
结合律

\[ \sum_{k\in K}(a_k+b_k) = \sum_{k\in K}a_k + \sum_{k\in K} b_k \]
交换律

\[ \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\sum_{d|\gcd(i,j)}d = \sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{\min(n,m)}[d|i] [d|j] d \]
替换指标变量
\[ \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) \]

一些常见的变换套路

黄金代换

\[ [\gcd(i,j)=1] = \sum_{d|\gcd(i,j)}\mu(d) \]
莫比乌斯函数性质的逆运用。
转艾佛森括号

\[ d|\gcd(i,j)\rightarrow [d|i][d|j] \]
以一式举例

\[\]
\[ \]
\[ \sum_{i=1}^n[d|i] = \lfloor \frac{n}{d} \rfloor \]
等号左边的实际意义就是让你求 \(1\sim n\) 中 \(d\) 的倍数的个数，那显然就是 \(\lfloor \frac{n}{d} \rfloor\) 个。
一个我也不知道叫啥的变换

\[ \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\)，来把下取整里面的两个变量转化为只有一个变量，方便我们进行整除分块。

狄利克雷卷积

定义

\(f(n),g(n)\) 是两个积性函数，那么

\[(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\) 是狄利克雷卷积的单位元。

JZTXT

初等数论（Ⅳ）：狄利克雷卷积和各类反演