定义
若数论函数 \(f\) 满足如下性质，我们称 \(f\) 为积性函数：
- \(f(1) = 1\)。
- 对于任意互素正整数 \(n, m\) 有 \(f(nm) = f(n)f(m)\)。
- （可选项）如果对于任意正整数 \(n, m\) 都有 \(f(nm) = f(n)f(m)\)，则称 \(f\) 为完全积性函数（没卵用）。
欧拉函数 \(\varphi(n)\)
定义
\(\varphi(n)\) 为不大于 \(n\) 的与 \(n\) 互素的数的个数，即： \[ \varphi(n) = \sum_{i = 1}^n \left[\gcd(i, n) = 1\right] \]
积性证明
我们证明对于任意正整数 \(n, m\) 若 \(\gcd(n, m) = 1\) 则 \(\varphi(mn) = \varphi(m)\varphi(n)\)：
首先我们把不大于 \(mn\) 的正整数排成 \(m\) 行 \(n\) 列的表： \[ \begin{matrix} 1 &m + 1 &\cdots &(n - 1)m + 1\\ 2 &m + 2 &\cdots &(n - 1)m + 2\\ \vdots &\vdots &\ddots &\vdots\\ m &2m &\cdots &nm \end{matrix} \] 由定义，\(\varphi(mn)\) 为这张表中与 \(mn\) 互素的数的个数。
因为表中的每一行模 \(m\) 同余，因此共有 \(\varphi(m)\) 行与 \(m\) 互素。
我们接下来证明：每一行的 \(n\) 个数模 \(n\) 两两不同余，因为假设在第 \(r\) 行存在两个数 \(am+r\) 和 \(bm + r\)，使得 \[ \begin{aligned} am + r &\equiv bm + r &\pmod n \\ (a - b)m &\equiv 0 &\pmod n \end{aligned} \] 因为 \(m,n\) 互素，因此 \(a - b \equiv 0 \pmod n\)，又因为 \(a, b < n\)，因此 \(a = b\)，矛盾。
因为每一行的 \(n\) 个数模 \(n\) 两两不同余，所以说虽然我不知道它们每个数模 \(n\) 是多少，但是我知道这些数模 \(n\) 一定构成了 \(0, 1, \cdots, n - 1\) 的一个排列。因此，因为 \(0, 1, \cdots, n-1\) 中有 \(\varphi(n)\) 个数与 \(n\) 互素，因此每一行中也有 \(\varphi(n)\) 个数与 \(n\) 互素。因此这 \(\varphi(m)\) 行与 \(m\) 互素的数中总共有 \(\varphi(m)\varphi(n)\) 个数与 \(mn\) 互素，因此 \(\varphi(mn) = \varphi(m)\varphi(n)\)，证毕。
在刚刚的证明中有一个非常重要的思想 —— 原来有 \(n\) 个数，对它们进行一定的变换，如果我们能够证明变换的结果两两不同，而且没变出其他的数，那么变换的结果一定是原来 \(n\) 个数的一个排列！
计算
单点计算
要探究 \(\varphi(n)\) 的计算公式，我们先探究 \(n = p^k\)，其中 \(p\) 为素数时的特例。在前 \(p^k\) 个正整数中共有 \(\frac{p^k}{p} = p^{k -1}\) 个数是 \(p\) 的倍数与 \(p^k\) 不互素，因此： \[ \varphi(p^k) = p^k - p^{k - 1} = p^k \left( 1 - \frac{1}{p}\right) \] 对于单个素数 \(p\)，有 \(\varphi(p) = p - 1\)。
接下来，我们利用 \(\varphi\) 的积性把上述公式拓展到一般情况，设 \(n\) 可以被素因数分解成 \(n = \prod_{i = 1}^r p_i^{c_i}\) 的形式，那么我们就有： \[ \begin{aligned} \varphi(n) &= \prod_{i = 1}^r \varphi(p_i^{c_i}) \\ &= \prod_{i = 1}^r p_i^{c_i} \left(1 - \frac{1}{p_i}\right) \\ &= \prod_{i = 1}^r p_i^{c_i} \prod_{i = 1}^r \left(1 - \frac{1}{p_i}\right) \\ &= n \prod_{i = 1}^r \left(1 - \frac{1}{p_i}\right) \end{aligned} \] 这就是欧拉函数的单点计算式，时间复杂度取决于素因数分解的时间复杂度，一般用试除法可以达到 \(O(\sqrt n)\)。
\([1, n]\) 计算
使用欧拉筛计算任何积性函数我们需要知道这个函数在以下三种点的取值：
- 在素数点的取值：\(\varphi(p) = p - 1\)
- 对于合数 \(n\) 和它的素因子 \(p\) 在 \(p \mid \frac{n}{p}\) 时的取值：由单点计算式，\(\varphi(n) = p\varphi(\frac{n}{p})\)
- 对于合数 \(n\) 和它的素因子 \(p\) 在 \(p \nmid \frac{n}{p}\) 时的取值：由积性，\(\varphi(n) = \varphi(p)\varphi(\frac{n}{p}) = (p - 1)\varphi(\frac{n}{p})\)
知道这三点信息之后我们就可以用欧拉筛完成在 \(O(n)\) 时间内计算 \([1, n]\) 内所有欧拉函数（或其他积性函数）的值：
bool v[N];
int phi[N];
int prime[P], tot = 0;
for (int i = 2; i <= n; i++) {
if (!v[i]) {
prime[++tot] = i;
phi[i] = i - 1; // 第一条
}
for (int j = 1; i * prime[j] <= n; j++) {
v[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j]; // 第二条
break;
} else
phi[i * prime[j]] = phi[i] * (prime[j] - 1); // 第三条
}
}前缀和计算
我们可以使用名为杜教筛的大佬专用工具在 \(O(n^{2 \over 3})\) 的时间复杂度计算出 \(\sum_{i = 1}^n \varphi(i)\) 的值。
欧拉定理
若正整数 \(a, n\) 互素，则 \(a^{\varphi(n)} \equiv 1 \pmod n\)。
证明：考虑与不大于 \(n\) 的与 \(n\) 互素的 \(\varphi(n)\) 个数： \[ x_1, x_2, \cdots, x_{\varphi(n)} \] 将它们同时乘以 \(a\)： \[ ax_1, ax_2, \cdots, ax_{\varphi(n)} \] 因为 \(a\) 与 \(n\) 互素，因此这些数依然和 \(n\) 互素。
接下来我们用证明欧拉函数积性时用到的方法，证明这些数模 \(n\) 两两不同余，假设存在 \(x_i,x_j\)，使得 \(ax_i \equiv ax_j \pmod n\)，那么因为 \(a, n\) 互素，\(x_i \equiv x_j \pmod n\)，矛盾。
因为这些数模 \(n\) 还是那几个与 \(n\) 互素的余数，而又两两不同余，这些数一定是 \(x_1, x_2, \cdots, x_{\varphi(n)}\) 的一个排列，既然如此，我们有： \[ \begin{aligned} \prod_{i = 1}^{\varphi(n)} x_i &\equiv \prod_{i = 1}^{\varphi(n)} ax_i &\pmod n \\ (a^{\varphi(n)} - 1) \prod_{i = 1}^{\varphi(n)} x_i &\equiv 0 &\pmod n\\ \end{aligned} \] 因为 \(\prod_{i = 1}^{\varphi(n)} x_i\) 与 \(n\) 互素，我们有： \[ \begin{aligned} a^{\varphi(n)} - 1 &\equiv 0 &\pmod n \\ a^{\varphi(n)} &\equiv 1 &\pmod n \end{aligned} \] 得证。
特例：当 \(n\) 时素数时，\(\varphi(n) = n - 1\)，因此我们有： \[ a^{n - 1} \equiv 1 \pmod n \] 即费马小定理。
莫比乌斯函数 \(\mu(n)\)
定义
设正整数 \(n\) 可以被素因数分解成 \(n = \prod_{i = 1}^r p_i^{c_i}\) 的形式，那么莫比乌斯函数的定义为： \[ \mu(n) = \begin{cases} 0 & \exists 1 \le i \le r, c_i > 1 \\ (-1)^r & \forall 1 \le i \le r, c_i \le 1 \end{cases} \] 即若 \(n\) 包含平方素因子，则 \(\mu(n) = 0\)，反之为 \(-1\) 的素因子个数次方。
积性证明
设正整数 \(m, n\) 互素，则：
- 若其中有一个包含平方素因子（一个的函数值为 \(0\)），则它们的积必定也包含这个平方素因子，函数值也为 \(0\)。
- 若两个都不包含平方素因子，则由于 \(m, n\) 互素（各自有不同的素因子），它们的积必定不包含平方素因子。不同素因子个数也一定为 \(m, n\) 不同素因子个数的和。
证毕。
计算
单点计算
见定义。
\([1, n]\) 计算
我们依然可以用欧拉筛在 \(O(n)\) 时间内计算出不大于 \(n\) 的所有 \(\mu\) 的值，代码如下：
bool v[N];
int mu[N];
int prime[P], tot = 0;
for (int i = 2; i <= n; i++) {
if (!v[i]) {
prime[++tot] = i;
mu[i] = -1; // 素数有一个素因子 (-1)^1
}
for (int j = 1; i * prime[j] <= n; j++) {
v[i * prime[j]] = true;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0; // 平方素因子
break;
} else
mu[i * prime[j]] = -mu[i]; // 多了一个素因子
}
}除数函数 \(\sigma(n)\)
定义
除数函数特指一大类的函数，对于正整数 \(n\)： \[ \sigma_x(n) = \sum_{d \mid n} d^x \] \(\sigma_0(n)\) 为 \(n\) 的约数个数，\(\sigma_1(n)\) 为 \(n\) 的约数和。
结论：\(\sigma_0(n) \sim O(n^{1 \over \ln\ln n})\)
积性证明
设 \(n, m\) 互素，则有： \[ \begin{aligned} \sigma_x(mn) &= \sum_{d_m \mid m}\sum_{d_n \mid n} (d_nd_m)^x \\ &= \sum_{d_m \mid m} d_m^x \sum_{d_n \mid n} d_n^x \\ &= \sigma_x(m)\sigma_x(n) \end{aligned} \] 注意这里我们在展开 \(\sigma_x(mn)\) 的时候利用了 \(m, n\) 互素这一点，如果 \(m, n\) 不互素则在这种写法中 \(mn\) 的某些因子会被计算多次，假设 \(m, n\) 有非平凡公因子 \(p\)，则 \(d_m = 1, d_n= p\) 和 \(d_m = p, d_n = 1\) 都可以令 \(d_md_n = p\)，\(p\) 就被计算了两次，结果就不对了。
计算
\(\sigma\) 这个东西在 OI 中存在感极低（说白了就是没卵用），因此对计算并不做要求。