积性函数的概念与判定
什么是积性函数?先看个生活例子
小明有10元钱,小红有5元钱,如果他们的钱放在一起,总数是15元——这是加法。但积性函数不一样,它像一种“混合配方”:假设你有一种香精浓度0.8,另一种浓度0.5,当两种互不影响的香精混合时,新的浓度是0.8×0.5 = 0.4。这就是乘法性质。
正式定义:设 fff 是一个定义在正整数上的函数。如果对于任意两个互质的正整数 aaa 和 bbb(即最大公约数 gcd(a,b)=1\gcd(a,b)=1gcd(a,b)=1),都有
f(ab)=f(a)⋅f(b)f(ab) = f(a) \cdot f(b)f(ab)=f(a)⋅f(b)
那么我们就称 fff 是一个积性函数。如果对任意正整数 aaa 和 bbb(不要求互质)上式都成立,则称 fff 是完全积性函数。
? 关键词:互质——两个数没有公共的质因子,比如 4 和 9(4=2²,9=3²)互质;而 6 和 8(6=2×3,8=2³)不互质,因为有公因子2。
为什么积性函数很重要?算得快!
很多数论函数都是积性函数,比如:
- 欧拉函数 φ(n)\varphi(n)φ(n):小于等于 n 且与 n 互质的数的个数。
- 莫比乌斯函数 μ(n)\mu(n)μ(n):常用于容斥原理和反演。
- 除数函数 d(n)d(n)d(n):n 的正因子个数。
- 除数之和函数 σ(n)\sigma(n)σ(n):n 的所有正因子之和。
这些函数如果直接按定义计算,对于大数(比如 10¹²)几乎不可能手动算。但利用积性,我们可以先分解质因数,再分别计算每个质因子幂次的函数值,最后乘起来。比如计算 φ(100)\varphi(100)φ(100):
100=22×52,φ(22)=22−21=2,φ(52)=52−51=20100 = 2^2 \times 5^2, \quad \varphi(2^2) = 2^2 - 2^1 = 2, \quad \varphi(5^2) = 5^2 - 5^1 = 20100=22×52,φ(22)=22−21=2,φ(52)=52−51=20
所以 φ(100)=2×20=40\varphi(100) = 2 \times 20 = 40φ(100)=2×20=40。如果不用积性,你得从1到100数出40个数,累死人。
怎么判定一个函数是积性函数?掌握三个要点
要证明 fff 是积性函数,通常需要三步:
- 检查 f(1)f(1)f(1) 的值:因为 f(1×n)=f(1)f(n)f(1 \times n) = f(1) f(n)f(1×n)=f(1)f(n),如果 fff 不恒为0,则必须 f(1)=1f(1) = 1f(1)=1。例如 φ(1)=1\varphi(1)=1φ(1)=1,d(1)=1d(1)=1d(1)=1,μ(1)=1\mu(1)=1μ(1)=1。
- 对任意互质的 a, b 证明等式成立:需要利用该函数的数学定义或性质。
- 小心陷阱:有些函数在 a, b 不互质时也可能满足 f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b),那就是完全积性函数,比如幂函数 f(n)=nkf(n)=n^kf(n)=nk。但大部分积性函数只对互质成立。
例子:欧拉函数为什么是积性的?
可以用“中国剩余定理”直观理解:因为 a 和 b 互质,所以模 ab 的剩余系(0到ab-1)与模 a 和模 b 的剩余系是一一对应的,且“与 ab 互质”的条件等价于“同时与 a 和 b 互质”,所以个数相乘。
例子:除数函数 d(n)d(n)d(n) 为什么是积性的?
若 n=p1e1p2e2⋯pkekn = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}n=p1e1p2e2⋯pkek,则 d(n)=(e1+1)(e2+1)⋯(ek+1)d(n) = (e_1+1)(e_2+1)\cdots(e_k+1)d(n)=(e1+1)(e2+1)⋯(ek+1)。这个公式本身就写成乘积形式,所以显然当 a 和 b 互质时,它们的质因子集合不重叠,因此 d(ab)=d(a)d(b)d(ab)=d(a)d(b)d(ab)=d(a)d(b)。
新手容易犯的错误
- ❌ 误认为所有积性函数都是完全积性:比如 φ(4)=2\varphi(4)=2φ(4)=2,但 φ(2)×φ(2)=1×1=1≠2\varphi(2)\times\varphi(2)=1\times1=1\neq2φ(2)×φ(2)=1×1=1=2,因为 2 和 2 不互质。所以欧拉函数只是积性,不是完全积性。
- ❌ 忘记检查 f(1)f(1)f(1):有些函数比如 f(n)=nf(n)=nf(n)=n 看起来像积性,但 f(1)=1f(1)=1f(1)=1 没问题;但若 f(n)=2nf(n)=2nf(n)=2n,则 f(1)=2≠1f(1)=2 \neq 1f(1)=2=1,所以它不是积性函数。
- ❌ 在代码中直接使用
result = result * (i - 1) / i导致整数除法丢失精度:应写成result = result / i * (i - 1)避免中间结果溢出或小数问题。 - ❌ 线性筛时忘记处理质数的情况:当 i 是质数时,phi[i]=i-1;当 i 是合数时,需要根据 i%p 是否等于0 来分类讨论。
完整示例:计算一个数的欧拉函数和除数函数
下面给出一个完整 C++ 程序,输入一个正整数 n,同时输出它的欧拉函数值 φ(n)\varphi(n)φ(n) 和除数函数值 d(n)d(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²,φ(100)=100×(1−1/2)×(1−1/5)=40\varphi(100)=100×(1-1/2)×(1-1/5)=40φ(100)=100×(1−1/2)×(1−1/5)=40,d(100)=(2+1)×(2+1)=9d(100)=(2+1)×(2+1)=9d(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)=1f(1)=1f(1)=1 和对互质数的乘法性质。编程中,我们常用质因数分解或线性筛来高效计算。
相关知识点指引:
- 如果你对莫比乌斯函数(μ(n)\mu(n)μ(n))和反演感兴趣,可以学习 莫比乌斯反演 和它的容斥应用。
- 想要处理更大范围(n≤1012n \leq 10^{12}n≤1012)的积性函数,可以了解杜教筛、Min_25筛等进阶技巧。
- 更深入的完全积性函数例子:幂函数 idk(n)=nkid_k(n)=n^kidk(n)=nk、常函数 1(n)=11(n)=11(n)=1 等。
试试自己证明除数函数 d(n)d(n)d(n) 是积性函数,并用上面的代码模板求 d(1000)d(1000)d(1000) 吧!