数论函数

在数论上，数论函数指定义域为正整数的函数。

积性与完全积性

如果一个数论函数 $f$ 满足 $\forall n, m \ge 1, \gcd(n, m) = 1 \ f(nm) = f(n)f(m)$ ，则称这个函数是积性的。

如果一个数论函数 $f$ 满足 $\forall n, m \ge 1 \ f(nm) = f(n)f(m)$ ，则称这个函数是完全积性的。

根据定义，所有完全积性函数的集合是所有积性函数的集合的子集。

一些重要的数论函数

$\varphi(n)$ 表示多少个数小于等于 $n$ 且与 $n$ 互质。
$\tau(n)$ 表示 $n$ 的约数个数。
$\sigma(n)$ 表示 $n$ 的约数之和。
$d_k(n)$ 表示约数 $k$ 次方和，即 $\sum_{d | n} d^k$ 。且 $\tau = d_0, \sigma = d_1$ 。
$\mu(n)$ 对于有平方因子的数为 $0$ ，否则有奇数 / 偶数个质因数时为 $-1 / 1$ 。
$\mathrm{Id}_k(n)$ 为 $n^k$ 。
$\epsilon(n)$ 为 $[n = 1]$ 。

可以证明，以上数论函数都是积性函数。

线性筛求积性函数

根据积性函数的定义，只要我们可以求出所有 $f(p^k)$ 的值（ $p$ 为质数， $k$ 为正整数），我们就可以用线性筛筛出积性函数 $f$ 。

举几个例子：假设 $n$ 的质因数分解为 $n = \prod_{i = 1}^m {p_i}^{a_i}$ ，那么：

根据积性函数的性质， $\varphi(n) = \prod_{i = 1}^m \varphi({p_i}^{a_i}) = \prod_{i = 1}^m ({p_i}^{a_i} - {p_i}^{a_i - 1})$ 。
根据积性函数的性质， $\tau(n) = \prod_{i = 1}^m \tau({p_i}^{a_i}) = \prod_{i = 1}^m (a_i + 1)$ 。
根据积性函数的性质， $\sigma(n) = \prod_{i = 1}^m \sigma({p_i}^{a_i}) = \prod_{i = 1}^m (1 + p_i + {p_i}^2 + \cdots + {p_i}^{a_i})$ 。

在 $\varphi$ 中， $\varphi(p^k) = p^k - p^{k - 1}$ ；在 $\tau$ 中， $\tau(p^k) = k + 1$ ；在 $\sigma$ 中， $\sigma(p^k) = 1 + p + p^2 + \cdots + p^k$ 。

这三个值都可以计算，所以它们可以用线性筛筛出。

那效率怎么样呢？我们知道，线性筛递推一次的时间复杂度为 $O(n)$ ，而 $1 \sim n$ 中大概有 $\dfrac{n}{\log n}$ 个形如 $p^k$ 的数，设求 $f(p^k)$ 的时间复杂度为 $t$ ，那么总时间复杂度为 $O(n + \dfrac{nt}{\log n})$ 。

所以，如果 $t$ 至多为为 $O(\log n)$ 级别，时间复杂度为线性。

数论函数的运用

公约数的和

求 $\sum_{j = 1}^n \sum_{i = j + 1}^n \gcd(i, j)$ 。

推一下柿子：

\begin{aligned} \sum_{j = 1}^n \sum_{i = j + 1}^n \gcd(i, j) &= \sum_{d = 1}^n d \sum_{j = 1}^n\sum_{i = j + 1}^n[\gcd(i, j) = d]\texttt{（枚举 gcd 的值 d）}\\ &= \sum_{d = 1}^n d \sum_{j = 1}^{\lfloor\frac dn\rfloor}\sum_{i = j + 1}^{\lfloor\frac dn\rfloor}[\gcd(i, j) = 1]\texttt{（i 变为 i / d，j 变为 j / d）}\\ &= \sum_{d = 1}^n d \sum_{i = 1}^{\lfloor\frac dn\rfloor}\sum_{j = 1}^{i - 1}[\gcd(i, j) = 1]\texttt{（由于 gcd 有交换律，所以可以交换 i, j）}\\ &= \sum_{d = 1}^n d\sum_{i = 1}^{\lfloor\frac dn\rfloor}\varphi(i)\texttt{（最后一个求和转变为欧拉函数）} \end{aligned}

线性筛出 $\varphi$ 并做前缀和即可线性求出答案。

上面推式子过程中枚举 $\gcd$ 是一个很重要的技巧。

例题

[SDOI2008] 仪仗队

[SDOI2008] 沙拉公主的困惑

GCD

Dirichlet 卷积

对于两个数论函数 $f, g$ ，它们的 Dirichlet 卷积 $h = f * g$ 被定义为 $h(n) = \sum_{d | n} f(d)g(n / d)$ 。

这个卷积满足交换律和结合律，则 $f * g = g * f, (f * g) * h = f * (g * h)$ 。

关于上面的数论函数，有一些性质：

$\epsilon * f = f$ ，其中 $f$ 为任意数论函数。（即， $\epsilon$ 是 Dirichlet 卷积的单位元）

证明

把卷积的式子写出来是这样的： $\sum_{d | n} \epsilon(d)f(n / d)$ 。只有 $d = 1$ 时 $\epsilon(d) = 1$ ，所以成立。
$d_k = \mathrm{Id}_k * \mathrm{Id}_0$ 。（我们还可以推出 $\tau = \mathrm{Id}_0 * \mathrm{Id}_0, \sigma = \mathrm{Id}_1 * \mathrm{Id}_0$ ）

证明

把卷积的式子写出来是这样的： $\sum_{i | n} i^k = d_k(n)$ ，与 $d_k$ 的定义一致。
$\varphi * \mathrm{Id}_0 = \mathrm{Id}_1$ 。

证明

想证明这个，其实就是证明 $\sum_{d | n} \varphi(d) = n$ 。

我们考虑下列 $n$ 个分数： $\dfrac 1n, \dfrac 2n, \dots, \dfrac nn$ 。

把它们都约分至最简形式。显然约分之后的分母只会是 $n$ 的因数。

对于每个因数 $x$ ，这些分数里分母为 $x$ 的分数显然有 $\varphi(x)$ 个。而且所有分数一共有 $n$ 个，所以原命题成立。
$\mu * \mathrm{Id}_0 = \epsilon$ （非常重要！）

证明

如果 $n$ 可以被质因数分解为 $n = \prod_{i = 1}^m {p_i}^{a_i}$ ，那么 $n$ 的一个约数 $d$ 可以被质因数分解为 $d = \prod_{i = 1}^m {p_i}^{b_i}$ ，且 $\forall i \in [1, m] \ 0 \le b_i \le a_i$ 。

如果有任意一个 $b_i \ge 2$ ，则 $\mu(d) = 0$ ，这是没有意义的，所以我们只考虑所有 $b_i \le 1$ 的情况。

如果 $m \ge 1$ （即 $n > 1$ ）， $b_i$ 之和为奇数与和为偶数的情况是一样的，都有 $2^{m - 1}$ 种，所以会抵消，即 $\sum_{d | n} \mu(d) = 0$ 。

否则， $\sum_{d | 1} \mu(d)$ 即为 $\mu(1) = 1$ 。

这与 $\epsilon$ 的定义一致，原命题成立。