数论函数与线性筛

数论函数把正整数映射为某种数值；
积性则允许我们从质数幂的局部信息恢复整个整数上的函数值。

1 从质因数分解到数论函数

算术基本定理把正整数唯一地分解为若干个质数幂，而积性函数进一步把整数上的函数值分解为各个质数幂上的局部贡献。

本章主线：数论函数 → 积性函数 → 质数幂上的局部贡献 → 线性筛的两种递推分支 → 欧拉函数与莫比乌斯函数 → 因数个数与因数和。

线性筛不仅可以批量找出质数，也可以在生成每个合数时顺便递推多种数论函数。

2 数论函数与积性

2.1 数论函数

定义域为正整数集合 $\mathbb N^+$ 的函数称为数论函数，通常写作 $f:\mathbb N^+\to S$ 。

常见例子包括：

欧拉函数 $\varphi(n)$ ：不超过 $n$ 且与 $n$ 互质的正整数个数；
莫比乌斯函数 $\mu(n)$ ：描述一个整数的质因数是否重复以及不同质因数的个数；
因数个数函数 $d(n)$ 或 $\tau(n)$ ；
因数和函数 $\sigma(n)$ 。

与映射的联系

数论函数本质上是以正整数为定义域的映射。

参见：03_映射

2.2 积性函数

若数论函数 $f$ 满足 $f(1)=1$ ，并且对任意互质的正整数 $a,b$ 都有 $f(ab)=f(a)f(b)$ ，则称 $f$ 为积性函数。

若不要求 $a,b$ 互质也始终满足这一等式，则称 $f$ 为完全积性函数。

例如，恒等函数 $\operatorname{id}(n)=n$ 是完全积性函数；而 $\varphi,\mu,d,\sigma$ 都是积性函数，但通常不是完全积性函数。

这里的互质条件不能省略，例如 $d(2)=2$ ，但 $d(4)=3\ne d(2)d(2)$ 。

2.3 质数幂上的局部贡献

设 $n$ 的标准质因数分解为 $\displaystyle n=\prod_{i=1}^{k}p_i^{a_i}$ 。

由于不同质数幂两两互质，若 $f$ 是积性函数，则 $\displaystyle f(n)=\prod_{i=1}^{k}f\left(p_i^{a_i}\right)$ 。

因此，一个积性函数只要确定了所有质数幂 $p^a$ 上的取值，就确定了它在全部正整数上的取值。

这也是线性筛递推积性函数的基础：加入一个新的质因数时，直接使用积性；增加已有质因数的指数时，只更新对应质数幂的局部贡献。

3 线性筛的统一递推框架

线性筛从小到大枚举整数 $i$ ，再枚举已经得到的质数 $p$ ，生成新整数 $i\cdot p$ 。

3.1 加入新的质因数

若 $p\nmid i$ ，则 $\gcd(i,p)=1$ 。

对于积性函数 $f$ ，可以直接得到 $f(ip)=f(i)f(p)$ 。

这相当于在 $i$ 的质因数分解中加入一个新的质因数 $p$ 。

3.2 增加已有质因数的指数

若 $p\mid i$ ，在线性筛中当前的 $p$ 就是 $i$ 的最小质因数。

设 $i=mp^e$ 且 $\gcd(m,p)=1$ ，则 $ip=mp^{e+1}$ 。

此时 $m$ 的贡献不变，只有最小质因数 $p$ 对应的局部贡献从 $f(p^e)$ 变为 $f(p^{e+1})$ ，因此需要根据具体函数单独递推。

代码中的结构统一为：

▶

线性筛递推框架

if( i % p == 0 ) {
    // 已有质因数 p 的指数增加
    // 根据具体函数递推
    break;
}
// 加入新的质因数 p

break 既保证每个合数只由最小质因数筛去一次，也把两种递推情况清楚地区分开来。

并不是所有积性函数都能在不知道额外信息时直接递推。
通常还需要能够在 $O(1)$ 时间内更新质数幂上的局部贡献，必要时维护指数、质数幂或局部函数值。

4 欧拉函数

4.1 定义与计算公式

欧拉函数 $\varphi(n)$ 表示 $1$ 到 $n$ 中与 $n$ 互质的正整数个数，并约定 $\varphi(1)=1$ 。

若 $\displaystyle n=\prod_{i=1}^{k}p_i^{a_i}$ ，则 $\displaystyle \varphi(n) = \prod_{i=1}^{k}p_i^{a_i-1}(p_i-1) = n\prod_{i=1}^{k}\left(1-\frac1{p_i}\right)$ 。

对于质数幂 $p^a$ ，在 $1$ 到 $p^a$ 中，不与 $p^a$ 互质的数恰好是 $p$ 的倍数，因此 $\varphi(p^a)=p^a-p^{a-1}$ 。

4.2 线性筛递推

设当前生成 $i\cdot p$ 。

若 $p\nmid i$ ，由积性得到 $\varphi(ip)=\varphi(i)\varphi(p)=\varphi(i)(p-1)$ 。

若 $p\mid i$ ，增加的只是质因数 $p$ 的指数吗，由于 $\varphi(p^{e+1})=p\varphi(p^e)$ ，因此 $\varphi(ip)=p\varphi(i)$ 。

所以

\varphi(ip)= \begin{cases} \varphi(i)(p-1), & p\nmid i,\\ p\varphi(i), & p\mid i. \end{cases}

5 莫比乌斯函数

5.1 定义

莫比乌斯函数定义为

\mu(n) = \begin{cases} 1, & n=1,\\ 0, & n\text{ 含有平方质因子},\\ (-1)^k, & n\text{ 是 }k\text{ 个不同质数的乘积}. \end{cases}

它只关注质因数是否重复，以及不同质因数个数的奇偶性。

5.2 线性筛递推

若 $p\nmid i$ ，则 $ip$ 新增了一个不同质因数，所以 $\mu(ip)=-\mu(i)$ 。

若 $p\mid i$ ，则 $p^2\mid ip$ ，因此 $\mu(ip)=0$ 。

所以

\mu(ip) = \begin{cases} -\mu(i), & p\nmid i,\\ 0, & p\mid i. \end{cases}

莫比乌斯函数在后续反演与互质计数中会把“最大公因数等于 $1$ ”转换为因数求和。

6 因数个数与因数和

因数个数和因数和的基本公式已经在 01_整数分解与筛法中给出，这里只关心它们如何在线性筛中递推。

6.1 因数个数

设 $d(i)$ 表示 $i$ 的正因数个数， $e(i)$ 表示 $i$ 的最小质因数在标准分解中的指数。

若 $p\nmid i$ ，则加入新的质因数 $p$ ，其指数为 $1$ ，所以 $d(ip)=2d(i)$ 。

若 $p\mid i$ ，设最小质因数 $p$ 在 $i$ 中的指数为 $e$ 。原来的局部贡献是 $e+1$ ，乘上一个 $p$ 后变成 $e+2$ ，因此 $\displaystyle d(ip)=d(i)\frac{e+2}{e+1}$ ，同时需要更新最小质因数指数： $e(ip)=e(i)+1$ 。

6.2 因数和

设 $\sigma(i)$ 表示 $i$ 的正因数和。

在线性筛中，再维护 $g(i)$ ，表示最小质因数对应的质数幂因数和。若最小质因数为 $p$ ，指数为 $e$ ，则

g(i)=1+p+p^2+\cdots+p^e.

若 $p\nmid i$ ，则新加入的局部贡献为 $1+p$ ，所以 $\sigma(ip)=\sigma(i)(1+p)$ ，并令 $g(ip)=1+p$ 。

若 $p\mid i$ ，则 $g(ip)=1+p+\cdots+p^{e+1}=pg(i)+1$

总因数和中其余质因数的贡献不变，因此 $\displaystyle \sigma(ip)=\frac{\sigma(i)}{g(i)}g(ip)$ 。

这里的 $g(i)$ 是最小质因数对应的整段等比和贡献。

7 线性筛实现

7.1 欧拉函数与莫比乌斯函数

▶

线性筛 - 欧拉函数与莫比乌斯函数

// 线性筛：素数 / phi / mu
int pri[maxn], pcnt;
bool isp[maxn];
ll phi[maxn];
int mu[maxn];
void sieve( int N ) {
    pcnt = 0;
    fill( isp, isp + N + 1, true );
    phi[1] = 1, mu[1] = 1;
    for( int i = 2; i <= N; ++ i ) {
        if( isp[i] ) pri[++ pcnt] = i, phi[i] = i - 1, mu[i] = -1;
        for( int j = 1; j <= pcnt && 1LL * i * pri[j] <= N; ++ j ) {
            int p = pri[j];
            isp[i * p] = 0;
            if( i % p == 0 ) {
                phi[i * p] = phi[i] * p;
                mu[i * p] = 0;
                break;
            }
            phi[i * p] = phi[i] * ( p - 1 );
            mu[i * p] = -mu[i];
        }
    }
}

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

7.2 因数个数与因数和

代码中使用 f[i] 表示因数和 $\sigma(i)$ ，使用 g[i] 表示最小质因数对应的等比和贡献。

▶

线性筛 - 因数个数与因数和

// 线性筛：因数个数 / 因数和
int pri[maxn], pcnt;
bool isp[maxn];
int d[maxn], e[maxn]; // 因数个数
int f[maxn], g[maxn]; // 因数和
void sieve2( int N ) {
    fill( isp + 2, isp + N + 1, true );
    d[1] = 1, f[1] = 1, g[1] = 1;
    for( ll i = 2; i <= N; ++ i ) {
        if( isp[i] ) {
            pri[++ pcnt] = i;
            e[i] = 1, d[i] = 2;
            g[i] = f[i] = i + 1;
        }
        for( ll j = 1; j <= pcnt && i * pri[j] <= N; ++ j ) {
            ll p = pri[j];
            isp[i * p] = 0;
            if( i % p == 0 ) {
                e[i * p] = e[i] + 1;
                d[i * p] = d[i] / e[i * p] * ( e[i * p] + 1 );
                g[i * p] = g[i] * p + 1;
                f[i * p] = f[i] / g[i] * g[i * p];
                break;
            }
            e[i * p] = 1;
            d[i * p] = d[i] * 2;
            g[i * p] = p + 1;
            f[i * p] = f[i] * g[i * p];
        }
    }
}

模板中 f、g 使用 int；若因数和可能超过范围，应按题目需要调整整数类型或取模。

8 与后续内容的联系

欧拉函数描述模乘法群的大小，并连接欧拉定理、阶与原根；
莫比乌斯函数是莫比乌斯反演和互质计数的核心工具；
积性函数在质数幂上的局部贡献会进一步抽象为狄利克雷卷积；
数论函数的前缀和可以通过整除分块与杜教筛加速计算；
线性筛预处理是多种数论求和算法的基础。