16 数论基础

GESP 5 级NOIP 进阶CSP-S

级别标注：GESP 5 级（考级要求）/ NOIP、CSP-J 进阶（竞赛进阶：质数筛、快速幂、取模、扩展欧几里得、组合数）。

一、质数与合数，sqrt 试除法

质数：大于 1 且只被 1 和自身整除。判断：

C++ 实例
#include <iostream>
#include <cmath>
using namespace std;

// 判断质数：只需试除到 sqrt(n)
bool isPrime(int n) {
    if (n < 2) return false;          // 0 和 1 不是质数
    for (int i = 2; (long long)i * i <= n; i++)   // i*i 防溢出用 long long
        if (n % i == 0) return false; // 能被整除 -> 合数
    return true;                      // 没有因子 -> 质数
}

注意用 i*i <= n 需防溢出，转 (long long)i*i。

质因数分解（试除法）

C++ 实例
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;                 // n 分解质因数
    for (int i = 2; (long long)i * i <= n; i++) {   // 从小到大试除
        while (n % i == 0) {         // 能整除就反复除干净
            cout << i << " ";
            n /= i;
        }
    }
    if (n > 1) cout << n;            // 剩余 n 是大于 sqrt 的质因子
    cout << endl;
    return 0;
}
形象理解判断质数像查户口本找“共犯”：如果 n 有因子，必有一个因子 ≤ √n，所以只试到 √n 就够。比如 101 只要试 2~10，不用试到 100。
易错点循环条件 i * i <= n 在 n 接近 10^9 时 i*i 会溢出 int。两种安全写法：(long long)i * i <= n 或 i <= n / i。GESP 5 级笔试常考这个坑。

二、质数筛：埃氏筛与欧拉筛

埃氏筛（O(n log log n)）

C++ 实例
#include <iostream>
using namespace std;
const int N = 1000005;
bool notPrime[N];            // false 表示是质数（埃氏筛标记数组）
void sieve(int n) {
    notPrime[0] = notPrime[1] = true;   // 0、1 不是质数
    for (int i = 2; (long long)i * i <= n; i++) {   // 只需筛到 sqrt(n)
        if (!notPrime[i]) {            // i 是质数
            for (int j = i * i; j <= n; j += i)     // 从 i*i 开始（更小的已筛过）
                notPrime[j] = true;      // 把 i 的倍数标记为合数
        }
    }
}
int main() {
    sieve(100);
    for (int i = 1; i <= 30; i++)
        if (!notPrime[i]) cout << i << " ";   // 2 3 5 7 11 13 17 19 23 29
    cout << endl;
    return 0;
}

线性筛（欧拉筛，O(n)，每个合数只被最小质因子筛一次，竞赛提速）

C++ 实例
#include <iostream>
#include <vector>
using namespace std;
const int N = 10000005;
int primes[N / 10], pc;      // 质数表（线性筛）
bool notPrime[N];
// 线性筛：每个合数只被它的最小质因数筛掉一次，O(n)
void linearSieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) primes[pc++] = i;      // i 是质数，收入质数表
        for (int j = 0; j < pc; j++) {           // 用已有质数筛 i 的倍数
            long long v = (long long)i * primes[j];
            if (v > n) break;                    // 超出范围
            notPrime[v] = true;
            if (i % primes[j] == 0) break;       // 保证每个合数只被最小质因数筛
        }
    }
}
形象理解埃氏筛像逐张划掉乘法表：先划掉 2 的所有倍数，再划掉 3 的倍数、5 的倍数…剩下没被划掉的就是质数。欧拉筛更精细：每个合数只被它的最小质因子划一次，所以是 O(n)。
考级视角埃氏筛标记起点是 j = i * i 而不是 2 * i：比 i 小的质数已经把更小的倍数划掉了。欧拉筛的 if (i % primes[j] == 0) break; 是保证“最小质因子只筛一次”的关键，笔试读程序题常考。

三、约数（因子）与最大公约数

求约数集合

C++ 实例
// 枚举 1..sqrt(n) 找成对约数（约数是成对出现的）
vector<int> getDivisors(int n) {
    vector<int> res;
    for (int i = 1; (long long)i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);            // 小约数 i
            if (i != n / i) res.push_back(n / i);   // 配对的大约数 n/i（避免平方重复）
        }
    }
    return res;
}

最大公约数 GCD（辗转相除法）

C++ 实例
// 最大公约数：辗转相除法，b 为 0 时 a 即答案
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// 最小公倍数：a / gcd(a,b) * b（先除再乘防溢出）
long long lcm(int a, int b) { return (long long)a / gcd(a, b) * b; }

扩展欧几里得（NOIP 进阶：解 ax + by = gcd(a,b)）

C++ 实例
// 扩展欧几里得：返回 gcd(a,b)，同时求出 x,y 使 ax + by = gcd(a,b)
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }   // 递归出口：a*1 + 0*0 = a
    long long g = exgcd(b, a % b, y, x);      // 递归时交换 x、y
    y -= a / b * x;                           // 回代修正 y
    return g;
}
形象理解GCD 辗转相除像用长条量地：用 b 量 a，剩 r；再用 r 量 b，再剩 r'…直到正好量完，最后的量尺就是最大公约数。gcd(a,b) = gcd(b, a%b)。
易错点算 lcm 一定要先除后乘：a / gcd(a,b) * b，写成 a * b / gcd(a,b) 会先溢出 int。另外 exgcd 的递归参数 exgcd(b, a%b, y, x) 里 x、y 是交换传入的，容易写错。

四、快速幂与取模

取模运算：(a + b) % m = (a%m + b%m) % m；乘：(a * b) % m = (a%m * b%m) % m。 注意：C++ 中负数取模结果是负数，需 ((x % m) + m) % m 修正。

C++ 实例
#include <iostream>
using namespace std;
// 快速幂：a^n % mod，O(log n)
long long fastPow(long long a, long long n, long long mod) {
    long long res = 1;
    a %= mod;                        // 先取模防溢出
    while (n > 0) {                  // 按二进制位处理指数
        if (n & 1) res = res * a % mod;   // 当前位为 1 才乘
        a = a * a % mod;             // a 平方（对应下一位的底）
        n >>= 1;                     // 指数右移
    }
    return res;
}
int main() {
    cout << fastPow(2, 10, 1000000007) << endl;   // 1024
    cout << fastPow(3, 100, 1000000007) << endl;
    return 0;
}

逆元（进阶：求分数在模意义下的值）

当 mod 为质数时，a 的乘法逆元为 fastPow(a, mod-2, mod)（费马小定理）。

C++ 实例
// 费马小定理求逆元：mod 为质数时，a 的逆元 = a^(mod-2) % mod
long long inv(long long a, long long mod) {
    return fastPow(a, mod - 2, mod);
}
// 组合数 C(n,k) = fact[n] * inv(fact[k]) % mod * inv(fact[n-k]) % mod
形象理解快速幂像翻倍算账法：算 3^100 不是乘 100 次，而是把指数写成二进制（100=64+32+4），底数不断自乘翻倍，只做 log 次乘法。每步取模保证数字不爆炸。
易错点三个坑：① a %= mod 开头要做，否则 a 可能超大；② res * a 可能溢出，全部用 long long 并每次 % mod；③ C++ 负数取模结果是负数，要写成 ((x % m) + m) % m。

五、组合计数基础

  • 阶乘与组合数（配合逆元/杨辉三角递推 C[i][j] = C[i-1][j] + C[i-1][j-1]）。
  • 排列数 P(n,k) = n!/(n-k)!。

六、易错点 / 常见坑点

  • ⚠️ 负数取模在 C++ 是负的，算术题务必修正为结果非负。
  • ⚠️ 判断质数时 i*i <= n 溢出（用 (long long) 或 i <= n / i）。
  • ⚠️ 快速幂里 res * a 可能溢出，用 long long 并 % mod。
  • ⚠️ 埃氏筛从 i * i 开始标记（小因子已在前面处理），别从 2*i 重复标记太多。
  • ⚠️ gcd 递归层级最深约 log 级别，别怕；但取模运算中除数为 0 时报错（b==0 时终止）。
  • ⚠️ 求组合数模大质数时直接阶乘会爆，需用逆元。
  • ⚠️ lcm(a,b) 先除后乘防溢出。

七、考级要求 vs 竞赛进阶

  • 考级要求（GESP 5 级）：质数判断、约数枚举、最大公约数/最小公倍数、简单取模运算、二进制/进制转换；部分考查埃氏筛概念。
  • 竞赛进阶（NOIP/CSP-J 提高）：线性筛、快速幂 + 取模、费马小定理逆元、扩展欧几里得、组合数取模、唯一分解定理在约数/和计算中的应用。

八、课内练习建议

  1. 手写 isPrime 并测试 10^6 附近的大数。
  2. 埃氏筛打印 1~1000 内所有质数。
  3. 用快速幂求 7^123456 % 1000000007。
  4. 求若干组 a、b 的 gcd / lcm（注意 long long）。
  5. 扩展：用 exgcd 求解 47x + 30y = 1 的一组整数解。
本章目录
一、质数与合数，sqrt 试除法 二、质数筛：埃氏筛与欧拉筛 三、约数（因子）与最大公约数 四、快速幂与取模 五、组合计数基础 六、易错点 / 常见坑点 七、考级要求 vs 竞赛进阶 八、课内练习建议