数论函数
积性函数
积性函数：对于任何互质的整数有 \(f(a \cdot b) = f(a) \cdot f(b)\) 的数论函数。
完全积性函数：对于任何整数有 \(f(a \cdot b) = f(a) \cdot f(b)\) 的数论函数。
常见积性函数：欧拉函数 \(\varphi\)，莫比乌斯函数 \(\mu\)，因数个数函数 \(\tau\)，因数和函数 \(\sigma\)。
\(\pi\) 函数不是积性函数。
性质 1 若 \(f(x), g(x)\) 均为积性函数，则 \(h(x) = f(x) \cdot g(x)\) 也为积性函数。
线性筛求积性函数
对于 \(p \mid n\)，\(f(n) = f(p) \cdot f(n / p)\)。
以欧拉函数为例：\(\varphi(n) = \varphi(p) \cdot \varphi(n / p)\)。
设素数 \(p\)，整数 \(x\)。
显然 \(\varphi(p) = p - 1\)；
若 \(p \nmid x\)，\(\varphi(px) = \varphi(p) \cdot \varphi(x)\)；
若 \(p \mid x\)，\(\varphi(px) = p \cdot \varphi(x)\)。
phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!vis[i]) {
primes.push_back(i);
phi[i] = i - 1;
}
for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
vis[i * primes[j]] = true;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
} else {
phi[i * primes[j]] = phi[i] * phi[primes[j]];
}
}
}
欧拉函数
欧拉函数 \(\varphi(n)\) 描述小于 \(n\) 的与 \(n\) 互素的正整数个数。
例如：\(\varphi(4) = 2\)。
欧拉函数是积性函数，线性筛求欧拉函数见上文“线性筛求积性函数”。
\[\varphi(n) = n \cdot \prod\limits_{p \mid n}{(1 - p^{-1})} \]欧拉定理 若正整数 \(a, p\) 互素，\(a^{\varphi(p)} \equiv 1 \pmod p\)。