初等数论概念梳理

作者：

fangys

一、概念与性质梳理

1. 素数与合数

素数：大于 1，只有 1 和自身两个正因数
合数：大于 1，有除 1 和自身外的其他因数
1 和 0：既非素数也非合数
判定：试除法 ( $O(\sqrt{n})$ )

2. 最大公约数（GCD）

若干数公共因数中的最大值
性质：( $\gcd(a, b) = \gcd(b, a\bmod b)$ )

3. 最小公倍数（LCM）

( $\mathrm{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$ )
注意：防止溢出（先除后乘）

4. 同余与模运算

( $a \equiv b \pmod{m}$ ) 表示 ( $m \mid a-b$ )
运算性质：
加法/乘法可分别取模
没有除法（需用逆元，但五级一般仅考同余基本概念）

5. 约数与倍数

( $d \mid n$ )：( d ) 是 ( n ) 的约数
通过质因数分解求约数个数、约数和

6. 质因数分解

唯一分解定理：( $n = p_1^{k_1} p_2^{k_2} \dots$ )

7. 奇偶性

加减：奇+奇=偶；奇+偶=奇；奇-奇=偶
乘：有偶则偶；全奇为奇

二、核心算法

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

gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

复杂度：( $O(\log \min(a,b))$ )
应用：求 GCD / LCM

2. 唯一分解定理

整数与质因数的双射关系
应用：
- 约数个数公式： $d(n) = (k_1+1)(k_2+1)\dots$
- 约数和公式： $\sigma(n) = \prod_{i}(1 + p_i + \dots + p_i^{k_i})$

3. 埃氏筛（Eratosthenes）

is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, sqrt(n)+1):
    if is_prime[i]:
        for j in range(i*i, n+1, i):
            is_prime[j] = False

复杂度：( $O(n \log \log n)$ )
特点：简单、空间适中、适合 n ≤ 1e7

4. 线性筛（欧拉筛）

primes = []
is_prime = [True] * (n+1)
for i in range(2, n+1):
    if is_prime[i]:
        primes.append(i)
    for p in primes:
        if i * p > n: break
        is_prime[i * p] = False
        if i % p == 0: break

复杂度：( $O(n)$ )
特点：每个合数只被最小质因子筛一次，适合 n ≤ 1e7~1e8

累加符号 ∑（Sigma）

含义：把一系列数加起来。

一般形式： $\sum_{i = 1}^{n} a_{i} = a_{1} + a_{2} + \dots + a_{n}$ $a_{i}$ 是通项公式

$i$ 是下标变量（从下界到上界，每次 +1）

累乘符号 ∏（Product）

含义：把一系列数乘起来。

一般形式： $\prod_{i = 1}^{n} a_{i} = a_{1} \times a_{2} \times \dots \times a_{n}$