积性函数：让复杂计算变简单的“乘法魔法”

什么是积性函数？先看个生活例子

小明有10元钱，小红有5元钱，如果他们的钱放在一起，总数是15元——这是加法。但积性函数不一样，它像一种“混合配方”：假设你有一种香精浓度0.8，另一种浓度0.5，当两种互不影响的香精混合时，新的浓度是0.8×0.5 = 0.4。这就是乘法性质。

正式定义：设 $f$ 是一个定义在正整数上的函数。如果对于任意两个互质的正整数 $a$ 和 $b$ （即最大公约数 $\gcd(a,b)=1$ ），都有

f(ab) = f(a) \cdot f(b)

那么我们就称 $f$ 是一个积性函数。如果对任意正整数 $a$ 和 $b$ （不要求互质）上式都成立，则称 $f$ 是完全积性函数。

? 关键词：互质——两个数没有公共的质因子，比如 4 和 9（4=2²，9=3²）互质；而 6 和 8（6=2×3，8=2³）不互质，因为有公因子2。

为什么积性函数很重要？算得快！

很多数论函数都是积性函数，比如：

欧拉函数 $\varphi(n)$ ：小于等于 n 且与 n 互质的数的个数。
莫比乌斯函数 $\mu(n)$ ：常用于容斥原理和反演。
除数函数 $d(n)$ ：n 的正因子个数。
除数之和函数 $\sigma(n)$ ：n 的所有正因子之和。

这些函数如果直接按定义计算，对于大数（比如 10¹²）几乎不可能手动算。但利用积性，我们可以先分解质因数，再分别计算每个质因子幂次的函数值，最后乘起来。比如计算 $\varphi(100)$ ：

100 = 2^2 \times 5^2, \quad \varphi(2^2) = 2^2 - 2^1 = 2, \quad \varphi(5^2) = 5^2 - 5^1 = 20

所以 $\varphi(100) = 2 \times 20 = 40$ 。如果不用积性，你得从1到100数出40个数，累死人。

怎么判定一个函数是积性函数？掌握三个要点

要证明 $f$ 是积性函数，通常需要三步：

检查 $f(1)$ 的值：因为 $f(1 \times n) = f(1) f(n)$ ，如果 $f$ 不恒为0，则必须 $f(1) = 1$ 。例如 $\varphi(1)=1$ ， $d(1)=1$ ， $\mu(1)=1$ 。
对任意互质的 a, b 证明等式成立：需要利用该函数的数学定义或性质。
小心陷阱：有些函数在 a, b 不互质时也可能满足 $f(ab)=f(a)f(b)$ ，那就是完全积性函数，比如幂函数 $f(n)=n^k$ 。但大部分积性函数只对互质成立。

例子：欧拉函数为什么是积性的？

可以用“中国剩余定理”直观理解：因为 a 和 b 互质，所以模 ab 的剩余系（0到ab-1）与模 a 和模 b 的剩余系是一一对应的，且“与 ab 互质”的条件等价于“同时与 a 和 b 互质”，所以个数相乘。

例子：除数函数 $d(n)$ 为什么是积性的？

若 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ ，则 $d(n) = (e_1+1)(e_2+1)\cdots(e_k+1)$ 。这个公式本身就写成乘积形式，所以显然当 a 和 b 互质时，它们的质因子集合不重叠，因此 $d(ab)=d(a)d(b)$ 。

新手容易犯的错误

❌ 误认为所有积性函数都是完全积性：比如 $\varphi(4)=2$ ，但 $\varphi(2)\times\varphi(2)=1\times1=1\neq2$ ，因为 2 和 2 不互质。所以欧拉函数只是积性，不是完全积性。
❌ 忘记检查 $f(1)$ ：有些函数比如 $f(n)=n$ 看起来像积性，但 $f(1)=1$ 没问题；但若 $f(n)=2n$ ，则 $f(1)=2 \neq 1$ ，所以它不是积性函数。
❌ 在代码中直接使用 result = result * (i - 1) / i 导致整数除法丢失精度：应写成 result = result / i * (i - 1) 避免中间结果溢出或小数问题。
❌ 线性筛时忘记处理质数的情况：当 i 是质数时，phi[i]=i-1；当 i 是合数时，需要根据 i%p 是否等于0 来分类讨论。

完整示例：计算一个数的欧拉函数和除数函数

下面给出一个完整 C++ 程序，输入一个正整数 n，同时输出它的欧拉函数值 $\varphi(n)$ 和除数函数值 $d(n)$ 。代码中每行变量都有中文注释。

#include <iostream>
#include <cmath>
using namespace std;

// 计算欧拉函数 phi(n) 和除数函数 d(n)
// 输入：正整数 n
// 输出：两个函数值
int main() {
    long long n;
    cout << "请输入一个正整数 n: ";
    cin >> n;
    
    long long temp = n;          // 临时变量，用于分解质因数
    long long phi_result = n;    // phi 的初始值 = n
    long long d_result = 1;      // d 的初始值 = 1（因子个数乘积）
    
    // 枚举所有可能的质因子 i（从2到 sqrt(temp)）
    for (long long i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {     // 找到质因子 i
            long long count = 0; // 记录 i 的幂次
            while (temp % i == 0) {
                temp /= i;
                count++;
            }
            // 更新欧拉函数：phi = phi / i * (i - 1)
            phi_result = phi_result / i * (i - 1);
            // 更新除数函数：d = d * (count + 1)
            d_result = d_result * (count + 1);
        }
    }
    // 如果最后剩下一个大于1的质因子
    if (temp > 1) {
        phi_result = phi_result / temp * (temp - 1);
        d_result = d_result * 2;  // 这个质因子的幂次为1，所以 (1+1)=2
    }
    
    cout << "欧拉函数 phi(" << n << ") = " << phi_result << endl;
    cout << "除数函数 d(" << n << ") = " << d_result << endl;
    
    return 0;
}

运行示例：

请输入一个正整数 n: 100
欧拉函数 phi(100) = 40
除数函数 d(100) = 9

解释：100=2²×5²， $\varphi(100)=100×(1-1/2)×(1-1/5)=40$ ， $d(100)=(2+1)×(2+1)=9$ 。

批量计算的利器：线性筛法

当我们需要计算1到N所有数的积性函数时，对每个数单独分解质因数太慢（复杂度 O(N√N)）。我们可以利用欧拉筛（线性筛）在 O(N) 时间内求出所有值。核心思想是：每个合数只被它的最小质因子筛掉一次，同时利用积性更新函数值。这里以欧拉函数为例，展示完整代码。

C++ 线性筛求 1 到 N 的欧拉函数

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000000;
long long phi[MAXN + 1];           // 存储每个数的欧拉函数值
int primes[MAXN];                  // 存储质数
int prime_count = 0;               // 质数个数
bool is_composite[MAXN + 1] = {false}; // 是否为合数

// 计算 1 到 n 所有数的欧拉函数
void compute_phi(int n) {
    phi[1] = 1;                    // 定义 phi(1)=1
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {    // i 是质数
            primes[prime_count++] = i;
            phi[i] = i - 1;        // 质数的 phi = 自身减1
        }
        // 用当前 i 和已有质数筛合数
        for (int j = 0; j < prime_count && i * primes[j] <= n; j++) {
            int p = primes[j];
            int cur = i * p;       // 当前要筛掉的合数
            is_composite[cur] = true;
            if (i % p == 0) {      // p 是 i 的最小质因子
                phi[cur] = phi[i] * p;   // 核心公式：phi(i*p) = phi(i) * p
                break;
            } else {               // p 与 i 互质
                phi[cur] = phi[i] * phi[p]; // 利用积性相乘
            }
        }
    }
}

int main() {
    int N;
    cout << "请输入 N: ";
    cin >> N;
    compute_phi(N);
    
    cout << "前10个欧拉函数值:" << endl;
    for (int i = 1; i <= min(N, 10); i++) {
        cout << "phi(" << i << ") = " << phi[i] << endl;
    }
    
    return 0;
}

Python 线性筛实现

MAXN = 1000000
phi = [0] * (MAXN + 1)           # 存储欧拉函数值
is_composite = [False] * (MAXN + 1)  # 是否为合数
primes = []                      # 质数列表

def compute_phi(n):
    phi[1] = 1                   # 定义 phi(1)=1
    for i in range(2, n + 1):
        if not is_composite[i]:  # i 是质数
            primes.append(i)
            phi[i] = i - 1       # 质数的 phi = 自身减1
        # 枚举质数，筛合数
        for p in primes:
            cur = i * p
            if cur > n:
                break
            is_composite[cur] = True
            if i % p == 0:       # p 是 i 的最小质因子
                phi[cur] = phi[i] * p
                break
            else:                # p 与 i 互质
                phi[cur] = phi[i] * (p - 1)

# 测试
N = int(input("请输入 N: "))
compute_phi(N)
print("前10个欧拉函数值:")
for i in range(1, min(N, 10) + 1):
    print(f"phi({i}) = {phi[i]}")

线性筛的常见错误：

忘记在 i % p == 0 时 break，导致重复筛和非积性更新错误。
忘记初始化 phi[1] = 1（有些函数需要，但欧拉函数必须）。
数组大小不够，导致越界。

积性函数的更多生活比喻

教室座位：假设学校有两个独立的教室A和B，A有10个座位，B有8个座位，并且A和B没有共用区域。那么总座位数 = 10 + 8 = 18（加法），不是积性。但如果是“相邻两间教室的隔音效果”，且隔音效果由墙壁材料决定：A的隔音系数0.9，B的隔音系数0.8，那么隔壁传来的声音衰减是0.9×0.8=0.72——这就是乘法，类似积性。
游戏装备：一个角色有两件互不冲突的装备，一件增加攻击力50%（系数1.5），另一件增加攻击力30%（系数1.3），那么总攻击力加成是1.5×1.3=1.95（即95%），而不是1.5+1.3=2.8（80%）。这里的“加成系数”就是完全积性函数。
排队问题：两个独立窗口，每个窗口每分钟处理人数分别为λ1和λ2，那么合并后的处理速率是λ1+λ2（加法）。但如果两个窗口的处理方式相互独立且互不影响，每个窗口的“错误率”相乘才得到总错误率——类似积性。

小结与下一步

积性函数是数论中的“瑞士军刀”，它能将复杂的大数计算化简为质因数分解后的简单乘法。判定一个函数是否为积性，关键在于验证 $f(1)=1$ 和对互质数的乘法性质。编程中，我们常用质因数分解或线性筛来高效计算。

相关知识点指引：

如果你对莫比乌斯函数（ $\mu(n)$ ）和反演感兴趣，可以学习莫比乌斯反演和它的容斥应用。
想要处理更大范围（ $n \leq 10^{12}$ ）的积性函数，可以了解杜教筛、Min_25筛等进阶技巧。
更深入的完全积性函数例子：幂函数 $id_k(n)=n^k$ 、常函数 $1(n)=1$ 等。

试试自己证明除数函数 $d(n)$ 是积性函数，并用上面的代码模板求 $d(1000)$ 吧！

积性函数的概念与判定