高效计算积性函数的线性筛算法与应用

核心逻辑与数学原理

积性函数与完全积性函数

若函数 $f(n)$ 的定义域为正整数，且对于任意满足 $ ext{gcd}(a, b) = 1$ 的正整数 $a, b$，均有：

$$f(a imes b) = f(a) imes f(b)$$

则称 $f(n)$ 为积性函数。若对于任意正整数 $a, b$（不要求互质），均有 $f(a imes b) = f(a) imes f(b)$，则称 $f(n)$ 为完全积性函数。

在 NOIP 竞赛中，最常需要处理的积性函数包括：

1. 莫比乌斯函数 $ u(n)$：

$$ u(n) = \begin{cases} 1 & n = 1 \ (-1)^k & n = p_1 p_2 \dots p_k \text{（各质因子互异）} \ 0 & \exists p, p^2 \mid n \end{cases}$$

2. 欧拉函数 $ ext{φ}(n)$：表示 $1 ext{到} n$ 中与 $n$ 互质的整数个数。其通项公式为：

$$\text{φ}(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

线性筛（欧拉筛）的核心机理

埃氏筛存在重复标记合数的冗余操作（如 $6$ 会被 $2$ 和 $3$ 各标记一次），时间复杂度为 $O(N \log \log N)$。线性筛（欧拉筛）通过严格控制每个合数只被其最小质因子标记一次，将时间复杂度压缩至极致的 $O(N)$。

其核心状态维持在一个扫描指针 $i$ 和当前的质数集合中。当扫描到 $i$ 时，遍历已知质数 $p_j$： 若满足 $i \bmod p_j == 0$，由于 $p_j$ 是从小到大遍历的，这意味着 $p_j$ 是 $i$ 的最小质因子。此时若继续向后标记 $i \cdot p_{j+1}$，由于 $i$ 包含质因子 $p_j$，那么 $i \cdot p_{j+1}$ 的最小质因子必然是 $p_j$ 而不是 $p_{j+1}$。为了防止重复标记，必须立刻 break 退出循环。

状态设计与算法推导

由于积性函数满足特殊的乘法性质，我们可以将其深度隐嵌入线性筛的执行流程中，在标记合数的同时，利用前驱状态以 $O(1)$ 的时间复杂度递推出当前合数的函数值。

1. 莫比乌斯函数 $

u(n)$ 的线性筛状态推导

• 边界：$ u(1) = 1$。
• 情况 A（$i$ 为质数）：$i$ 自身只有一个质因子，根据定义 $ u(i) = -1$。
• 情况 B（$i \bmod p_j \neq 0$）：此时 $p_j$ 与 $i$ 互质。由积性函数性质得：

$$\nu(i \cdot p_j) = \nu(i) \cdot \nu(p_j) = -\nu(i)$$

• 情况 C（$i \bmod p_j == 0$）：此时 $i \cdot p_j$ 至少包含两个相同的质因子 $p_j$（即 $p_j^2 \mid (i \cdot p_j)$），根据定义，其值直接归零：

$$\nu(i \cdot p_j) = 0$$

2. 欧拉函数 $ ext{φ}(n)$ 的线性筛状态推导

• 边界：$ ext{φ}(1) = 1$。
• 情况 A（$i$ 为质数）：$1 \sim i-1$ 均与 $i$ 互质，故 $ ext{φ}(i) = i - 1$。
• 情况 B（$i \bmod p_j \neq 0$）：$p_j$ 与 $i$ 互质，由积性性质得：

$$\text{φ}(i \cdot p_j) = \text{φ}(i) \cdot \text{φ}(p_j) = \text{φ}(i) \cdot (p_j - 1)$$

• 情况 C（$i \bmod p_j == 0$）：此时 $p_j$ 是 $i$ 的因子，说明 $i$ 已经包含了 $i \cdot p_j$ 的所有质因子种类。带入通项公式变形：

$$\text{φ}(i \cdot p_j) = (i \cdot p_j) \prod_{p \mid (i \cdot p_j)} \left(1 - \frac{1}{p}\right) = p_j \cdot \left[ i \prod_{p \mid i} \left(1 - \frac{1}{p}\right) \right] = p_j \cdot \text{φ}(i)$$

C++ 标准源码

#include <iostream>
#include <vector>

const int MAXN = 2000000; // 模拟 NOIP 标准全局规模

int primes[MAXN + 5], cnt;
bool is_not_prime[MAXN + 5]; // 状态取反：false 表示是质数，利于节省 memset 或默认初始化时间
int mu[MAXN + 5];
int phi[MAXN + 5];

void sieve(int n) {
    is_not_prime[0] = is_not_prime[1] = true;
    mu[1] = 1;
    phi[1] = 1; // 必须手动初始化边界状态
    cnt = 0;

    for (int i = 2; i <= n; ++i) {
        if (!is_not_prime[i]) {
            primes[cnt++] = i;
            mu[i] = -1;       // 质数只有一个质因子
            phi[i] = i - 1;   // 质数的欧拉函数值为 i - 1
        }
        for (int j = 0; j < cnt && i * primes[j] <= n; ++j) {
            int target = i * primes[j];
            is_not_prime[target] = true; // 标记合数

            if (i % primes[j] == 0) {
                mu[target] = 0;                  // 存在平方因子，莫比乌斯函数值必为 0
                phi[target] = phi[i] * primes[j]; // 质因子种类未变，欧拉函数直接乘以 primes[j]
                break; // 线性筛致命核心：保证每个合数只被其最小质因子筛去
            } else {
                mu[target] = -mu[i];                            // 互质情况，新增一个异异质因子，符号取反
                phi[target] = phi[i] * (primes[j] - 1);         // 互质情况，直接利用积性性质相乘
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    if (std::cin >> n) {
        if (n > MAXN) n = MAXN; // 防御性越界拦截
        sieve(n);
        // 输出前 10 个结果进行验证
        for (int i = 1; i <= std::min(n, 10); ++i) {
            std::cout << "i=" << i << " | mu=" << mu[i] << " | phi=" << phi[i] << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 线性筛内部漏写 break 或写错位置 如果在 i % primes[j] == 0 条件分支中漏写 break，合数将会被后续更大的质因子重复筛除。算法的时间复杂度会瞬间退化到 $O(N \log \log N)$ 甚至接近 $O(N^2)$，在 NOIP 极限 $10^7$ 的数据下会导致直接超时 TLE。
2. 数组越界溢出风险 在内层循环中，控制条件必须严格写为 i * primes[j] <= n，不能仅靠 j < cnt 来拦截。如果不做乘法边界限制，i * primes[j] 会直接越界访问并篡改内存，引发不可预知的段错误（Segmentation Fault）或计算出垃圾值。

经典 NOIP/洛谷 真题

1. 洛谷 P3812 【模板】线性基 / 类似数论变式 P2158 [SDOI2008] 仪仗队

• 题意描述：在一个 $N \times N$ 的方阵中，计算从左下角 $(0,0)$ 处能够看到的人数（即两点连线上没有其他人挡住）。
• 问题本质：计算满足 $ ext{gcd}(x, y) = 1$ 的二元组 $(x, y)$ 的对数。
• 核心解题思路：除了边界 $(1,0)$ 和 $(0,1)$，方阵具有对称性。对于一侧，当横坐标为 $x$ 时，纵坐标 $y < x$ 且与 $x$ 互质的个数正是欧拉函数 $ ext{φ}(x)$ 的定义。因此答案本质上就是 $3 + 2 \times \sum_{i=2}^{N-1} \text{φ}(i)$。直接调用线性筛预处理出整个 $ ext{φ}$ 数组，然后前缀和累加即可在 $O(N)$ 内破局。

2. 洛谷 P3455 [POI2007] ZAP-Queries

• 题意描述：给定 $a, b, d$，求满足 $1 \le x \le a, 1 \le y \le b$ 且 $ ext{gcd}(x, y) = d$ 的数对 $(x, y)$ 有多少对。多组询问。
• 问题本质：莫比乌斯反演基础应用。
• 核心解题思路：等价于求 $\sum_{i=1}^{\lfloor a/d \rfloor} \sum_{j=1}^{\lfloor b/d \rfloor} [\text{gcd}(i, j) == 1]$。利用莫比乌斯函数的性质 $\sum_{d \mid n} \nu(d) = [n==1]$ 进行性质替换，可将方程最终推导为：

$$\sum_{T=1}^{\min(\lfloor a/d \rfloor, \lfloor b/d \rfloor)} \nu(T) \cdot \lfloor \frac{a}{d \cdot T} \rfloor \cdot \lfloor \frac{b}{d \cdot T} \rfloor$$

通过线性筛在 $O(N)$ 内预处理出 $ u$ 函数并建立前缀和，配合整除分块（数论分块）技术，可在 $O(\sqrt{N})$ 的时间内响应单次询问。