数论基础 — GCD、素数与欧拉函数

前言：整数的“原子结构”

你可能很早就学过素数、公约数这些概念。在日常生活中，知道”6 和 15 的最大公约数是 3”就够了。但在算法题里，这些概念变成了工具——你需要用它们来解决问题。

举几个例子：

• “把 $n$ 个糖果平均分给 $k$ 个人，每人最多分几个，还剩几个？“——这是取模运算，但你可能还需要知道剩余的糖果能不能再平均分下去，这就涉及了 $\gcd$。
• “判断一个大数是不是素数”——直接试除太慢了，有没有更快的方法？
• “从 1 到 $n$ 中，有多少个数和 $n$ 互素？“——这引出了欧拉函数，它是密码学（比如 RSA）的基石。

这篇笔记的核心线索是整数的分解。就像物质由原子组成一样，每个整数都可以唯一分解为素数的乘积（算术基本定理）。围绕这个事实，我们能推导出一系列有用的工具：

1. GCD 与辗转相除 —— 怎么快速求最大公约数
2. 素数筛 —— 怎么快速找出所有素数
3. 欧拉函数 —— 怎么快速算出”与 $n$ 互素的数有多少个”
4. 约数计数 —— 怎么从素因子分解出发计算约数个数和约数和

这些工具看起来零散，但它们都建立在同一个基础之上：整数的素因子分解。最后我们会用一道综合题，把这些工具串起来。

一、最大公约数与最小公倍数

1.1 辗转相除法（欧几里得算法）

$$\gcd(a, b) = \gcd(b, a \bmod b), \quad b \ne 0$$

每步至少把较大的数减半，所以迭代次数 $O(\log(\max(a,b)))$。

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

C++17 起标准库有 std::gcd，但理解原理是必要的——因为很多扩展算法直接基于它。

1.2 为什么 $\gcd(a,b) = \gcd(b, a \bmod b)$？

设 $d = \gcd(a, b)$。则 $d \mid a$ 且 $d \mid b$。而 $a \bmod b = a - \lfloor a/b \rfloor \cdot b$，所以 $d$ 也整除 $a \bmod b$。反过来，任何同时整除 $b$ 和 $a \bmod b$ 的数也整除 $a = b \cdot \lfloor a/b \rfloor + (a \bmod b)$。所以两对数的公约数集合完全相同，最大值自然相同。

1.3 LCM

$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$

注意先除后乘防溢出：a / gcd(a, b) * b。

1.4 扩展欧几里得算法

上面我们只是计算了 $\gcd$。但有时候我们需要知道更多信息——比如”$a$ 和 $b$ 的 $\gcd$ 能不能表示成 $ax + by$ 的形式？“答案是可以，而且辗转相除的过程中可以顺便求出 $x$ 和 $y$。

递归推导：假设已知 $\gcd(b, a \bmod b)$ 对应的解 $(x', y')$，即 $bx' + (a \bmod b)y' = \gcd(a, b)$。代入 $a \bmod b = a - \lfloor a/b \rfloor \cdot b$：

$$bx' + (a - \lfloor a/b \rfloor \cdot b)y' = ay' + b(x' - \lfloor a/b \rfloor \cdot y')$$

所以 $x = y'$，$y = x' - \lfloor a/b \rfloor \cdot y'$。

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

用途：求逆元（$ax \equiv 1 \pmod{m}$ 即 $ax + my = 1$，用 exgcd 解）、解线性同余方程、解线性丢番图方程。

二、素数

2.1 定义与基本性质

素数是大于 1 且恰好有两个正因子（1 和自身）的整数。

• 前 20 个素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
• 算术基本定理：每个 $> 1$ 的整数可以唯一地分解为素数的乘积
• 小于 $n$ 的素数约有 $n / \ln n$ 个（素数定理）

2.2 埃拉托斯特尼筛法

要判断一个数是否为素数，可以试除到 $\sqrt{n}$。但如果需要知道 $1$ 到 $n$ 中所有素数呢？逐个试除太慢了。筛法的思路完全不同：不问”这个数是不是素数”，而是”把所有合数标记出来，剩下的就是素数”。

从 2 开始，每遇到一个素数就把它的所有倍数标记为合数。

bool is_composite[MAXN];
vector<int> primes;

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

这是线性筛（欧拉筛）：每个合数只被它的最小素因子筛一次，总时间 $O(n)$。

if (i % primes[j] == 0) break 是关键——当 $i$ 是 primes[j] 的倍数时，primes[j] 就是 $i$ 的最小素因子，后续更大的素数与 $i$ 的乘积会被更小的素因子先筛掉，所以可以 break。

2.3 素性测试

对单个大数 $n$ 判断是否为素数：

• 试除法：枚举到 $\sqrt{n}$，$O(\sqrt{n})$
• Miller-Rabin：随机化算法，$O(k \log^3 n)$，$k$ 轮后错误概率 $\le 4^{-k}$

竞赛中，$n \le 10^{18}$ 时，用一组特定的基 $\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}$ 即可 100% 正确判定。

三、欧拉函数

3.1 定义

$\varphi(n)$：$1$ 到 $n$ 中与 $n$ 互素的正整数个数。

$$\varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)$$

其中 $p$ 遍历 $n$ 的所有不同素因子。

例如 $\varphi(12) = 12 \cdot (1 - 1/2)(1 - 1/3) = 4$。验证：$1, 5, 7, 11$，确实 4 个。

3.2 积性

若 $\gcd(a, b) = 1$，则 $\varphi(ab) = \varphi(a)\varphi(b)$。

这直接来自定义——$a$ 和 $b$ 的素因子集不相交，两个乘积直接合并。所以只需知道素数幂的欧拉函数值：

$$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$$

直觉：$1$ 到 $p^k$ 中与 $p^k$ 不互素的数恰好是 $p$ 的倍数，共 $p^{k-1}$ 个。

3.3 欧拉定理

若 $\gcd(a, n) = 1$，则 $a^{\varphi(n)} \equiv 1 \pmod{n}$。

费马小定理是它在 $n$ 为素数时的特例（$\varphi(p) = p - 1$）。

意义：费马小定理只对素数模数有效，但实际题目中模数不一定是素数。欧拉定理给出了更一般的周期——只要 $a$ 和 $n$ 互素，$a$ 的幂次每 $\varphi(n)$ 步回到 1。

意义：提供了模非素数的指数周期。当模数不是素数但与 $a$ 互素时，用 $\varphi(n)$ 代替 $p - 1$ 即可。

3.4 用线性筛求欧拉函数

int phi[MAXN];
bool is_composite[MAXN];
vector<int> primes;

void phi_sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            phi[i] = i - 1;  // 素数：φ(p) = p - 1
        }
        for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                // primes[j] | i，最小素因子的幂次增加
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                // 积性
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

当 primes[j] | i 时，$i \cdot p_j$ 与 $i$ 有完全相同的素因子集，只是 $p_j$ 的幂次多了 1。由 $\varphi(p^k) = p^{k-1}(p-1)$ 的递推关系，$\varphi(i \cdot p_j) = \varphi(i) \cdot p_j$。

当 primes[j] ∤ i 时，$\gcd(i, p_j) = 1$，由积性直接 $\varphi(i \cdot p_j) = \varphi(i) \cdot \varphi(p_j) = \varphi(i) \cdot (p_j - 1)$。

四、求约数个数与约数和

对 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$：

量	公式	直觉
约数个数	$\prod_{i=1}^{k}(a_i + 1)$	每个素因子的幂次选 $0$ 到 $a_i$
约数和	$\prod_{i=1}^{k}\frac{p_i^{a_i+1}-1}{p_i - 1}$	每个素因子贡献等比数列之和

也可以在筛的过程中同时求出，利用积性维护每个数的最小素因子的幂次。

五、实战：求 $\sum_{i=1}^{n} \gcd(i, n)$

给定 $n$（$1 \le n \le 10^6$），求 $\sum_{i=1}^{n} \gcd(i, n)$。

朴素 $O(n \log n)$ 可以过，但有个 $O(\sqrt{n})$ 的数论做法。

把求和按 $\gcd$ 的值分类：

$$\sum_{i=1}^{n}\gcd(i, n) = \sum_{d \mid n} d \cdot |\{i : 1 \le i \le n,\ \gcd(i, n) = d\}|$$

$\gcd(i, n) = d \iff \gcd(i/d, n/d) = 1$，所以满足条件的 $i$ 恰好有 $\varphi(n/d)$ 个：

$$= \sum_{d \mid n} d \cdot \varphi\left(\frac{n}{d}\right)$$

枚举 $n$ 的所有约数 $d$，对每个约数查 $\varphi(n/d)$，累加即可。

#include <cstdio>
using namespace std;

const int MAXN = 1000006;
int phi[MAXN];
bool is_comp[MAXN];
int primes[80000], pcnt;

void sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_comp[i]) { primes[pcnt++] = i; phi[i] = i - 1; }
        for (int j = 0; j < pcnt && (long long)i * primes[j] <= n; j++) {
            is_comp[i * primes[j]] = true;
            if (i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    sieve(n);

    long long ans = 0;
    for (int d = 1; (long long)d * d <= n; d++) {
        if (n % d == 0) {
            ans += (long long)d * phi[n / d];
            if (d != n / d)
                ans += (long long)(n / d) * phi[d];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

解析：核心是把”求和”转化为”按 $\gcd$ 值分类”，然后发现每一类的计数就是 $\varphi$。枚举约数只需 $O(\sqrt{n})$（对每个 $d$ 检查 $d$ 和 $n/d$），配合 $O(n)$ 的欧拉函数预处理，总体效率远优于逐项计算。