冲刺阶段：数学数论精讲 - 莫比乌斯反演与容斥原理实战

在蓝桥杯等数学竞赛中，数论部分常常是考察的重点之一。特别是莫比乌斯反演与容斥原理，这两个知识点在解决复杂问题时具有极高的效率。本文将通过约数统计问题，详细演示预处理莫比乌斯函数的步骤，并结合容斥原理，帮助大家在冲刺阶段更好地掌握这两个重要工具。

一、莫比乌斯函数简介

莫比乌斯函数μ(n)是一个定义在正整数上的函数，其值只可能是-1、0或1。具体定义如下：
- μ(n) = 1，如果n是无平方因子数且有偶数个不同的质因数。
- μ(n) = -1，如果n是无平方因子数且有奇数个不同的质因数。
- μ(n) = 0，如果n有平方因子。

二、预处理莫比乌斯函数

在解决约数统计等问题时，预先计算出莫比乌斯函数的值可以大大提高效率。以下是预处理莫比乌斯函数的步骤：

初始化数组：创建一个大小为N的数组mu，初始化为1。
筛法计算：使用线性筛法（埃拉托斯特尼筛法的改进版）计算莫比乌斯函数值。

对于每个质数p，更新所有p的倍数的mu值。
如果某个数n是p的平方的倍数，则mu[n]设为0。
否则，根据n的质因数个数更新mu[n]的值。

const int N = 1000000;
int mu[N + 1], prime[N + 1], cnt;
bool vis[N + 1];

void init_mu() {
    mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= N; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            } else {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}