数学

没问题！模拟赛留着等你有整块时间、能专注认真做的时候再战——那样检验效果才真实，也更有比赛的感觉。到时候把代码发我，我给你当评测机 + 教练。👍

那我们继续往后推进，进入 第五部分：数学。先给你交代一下这部分的定位和路线：

第五部分预览：数学

数学题在铜牌里时常出现，而且有个特点——会就是会、不会就卡死，因为很多是"知道公式/模板就秒，不知道就无从下手"。所以这部分的策略是把高频模板和经典结论吃透。

好消息是你已经有基础了：

• 快速幂你在 1.6 学过了（递归分治版）
• GCD 你在 1.1 见过 __gcd
• 高精度你之前自己做过

按大纲，第五部分的核心是：

• 5.1 数论基础：GCD/LCM、快速幂、快速乘
• 5.2 素数：筛法、分解质因数
• 5.3 同余与逆元：费马小定理、扩展欧几里得、逆元
• 5.4 组合数学：排列组合、组合数取模
• 5.5 高精度（你有基础，快速过）

其中 5.1（数论基础）和 5.2（素数筛）是铜牌最常用的，5.3、5.4 是进阶（组合数取模在计数题里会用）。

我们从 5.1 数论基础 开始。这一节会把 GCD/LCM、快速幂（复习+巩固）、快速乘讲透，都是高频且模板固定的内容。

要我现在开始讲 5.1 数论基础 吗？还是你想跳过某些数学内容、直接挑你觉得最需要的部分？（比如有些人觉得数论用得少，想先巩固 DP/图论——你的 EEG/BCI 和竞赛背景里，如果数论需求不高，我们也可以按你的实际需要调整顺序。）

先建立认知：

数论基础就是一套固定的小工具：求最大公约数、求幂取模、防止乘法溢出等。它们本身不难，但经常作为更大问题的组成部分出现（比如组合数取模要用快速幂求逆元）。把这几个模板背到能默写，是数论题的前提。

一、GCD（最大公约数）与 LCM（最小公倍数）

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

最大公约数：两个数的最大公共因子。求法是辗转相除法——核心结论：gcd(a, b) = gcd(b, a % b)，直到余数为 0。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);   // 余数为0时，a 就是答案
}

理解：gcd(12, 8) → gcd(8, 4) → gcd(4, 0) → 4。每次用"较小数"和"两数取余"递归，余数不断变小，最终余数为 0 时，被除数就是最大公约数。

C++ 有内置函数 __gcd(a, b)（接 1.1），直接用即可，不用手写。但理解辗转相除的原理，因为扩展欧几里得（5.3）基于它。

solution.cpp

int g = __gcd(a, b);   // 内置，最方便

LCM：最小公倍数

最小公倍数通过 GCD 求：lcm(a, b) = a / gcd(a, b) * b。

long long lcm(long long a, long long b) {
    return a / __gcd(a, b) * b;    // 注意：先除后乘，防溢出！
}

重要细节（防溢出，接 0.2）：写成 a / gcd * b 而不是 a * b / gcd！因为 a * b 可能先溢出。先除再乘能避免中间结果过大。这是 LCM 的经典坑。而且 LCM 容易很大，用 long long。

GCD 的常见应用

• 约分分数：分子分母同除以 gcd。
• 判断互质：gcd(a,b) == 1 说明互质。
• 多个数的 gcd：依次求，gcd(gcd(a,b),c)。

// 求多个数的 gcd
int g = a[0];
for (int i = 1; i < n; i++) g = __gcd(g, a[i]);

二、快速幂（复习 + 巩固，必背）

你在 1.6 学过快速幂的递归版，这里复习并给出迭代版（更常用、不会栈溢出）。

解决什么问题

求 a^b mod p，其中 b 可能很大（如 10⁹）。朴素连乘 O(b) 会超时，快速幂 O(log b)。

核心思想（复习）

利用 a^b = (a^(b/2))²，每次把指数减半。或者从二进制角度：把 b 拆成二进制，a^b = 各个二进制位对应的 a^(2^k) 的乘积。

迭代版快速幂（推荐，背下来）

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;                    // 先取模，防止 a 本身很大
    while (b > 0) {
        if (b & 1)             // 当前二进制位是1
            res = res * a % p; // 累乘这一位对应的 a 的幂
        a = a * a % p;         // a 自乘（a^1 → a^2 → a^4 → ...）
        b >>= 1;               // b 右移一位（处理下一个二进制位）
    }
    return res;
}

理解迭代版：

• b & 1 判断 b 的最低位是不是 1（这一位要不要乘）。
• a = a * a % p 让 a 依次变成 a, a², a⁴, a⁸...（对应二进制每一位的权值）。
• b >>= 1 把 b 右移，处理下一位。
• 每步都取模，且用 long long 防溢出（接 0.2 取模乘法）。

举例：a^13，13 = 1101₂ = 8+4+1，所以 a^13 = a^8 · a^4 · a^1。迭代时 b 的二进制位为 1 的位置（第0、2、3位），就把对应的 a^(2^k) 乘进结果。

快速幂是数论第一高频模板，必须背到能默写。迭代版比递归版更常用（不会栈溢出、稍快）。理解"二进制拆分指数"的思想 + 记住模板。后面求逆元、组合数取模、矩阵快速幂都依赖它。

快速幂的应用

• 大数幂取模：直接用。
• 求逆元（5.3）：费马小定理 a^(p-2) mod p 就是 a 的逆元，用快速幂算。
• 矩阵快速幂（拓展）：把数换成矩阵，能快速求线性递推（如斐波那契第 n 项）。

三、快速乘（防止乘法溢出，了解）

解决什么问题

当两个数 a、b 都很大（接近 long long 上限，如 10¹⁸），a * b 即使用 long long 也会溢出。快速乘用类似快速幂的思想，把乘法拆成加法，避免溢出。

核心思想

a * b = 把 b 二进制拆分，a * b = Σ a·(2^k)，用加法累加（加法不会溢出，或用 __int128 兜底）。

long long qmul(long long a, long long b, long long p) {
    long long res = 0;
    a %= p;
    while (b > 0) {
        if (b & 1) res = (res + a) % p;   // 加上这一位对应的 a
        a = (a + a) % p;                   // a 翻倍（用加法，不溢出）
        b >>= 1;
    }
    return res;
}

快速乘用于"两个大数相乘取模会溢出"的情况。结构和快速幂一模一样，只是把"乘"换成"加"。

实战中更简单的办法：C++ 有 __int128（128 位整数），直接 (__int128)a * b % p 就能防溢出，比快速乘简洁：

solution.cpp

long long res = (__int128)a * b % p;   // 用128位整数兜底，最简单

铜牌阶段，遇到大数乘法溢出，优先用 (__int128) 强转，比手写快速乘方便。快速乘了解思想即可。

四、其他常用小结论（积累）

数论里一些零碎但有用的结论：

• 判断奇偶：x & 1 为 1 是奇数，0 是偶数（接 0.3 位运算，记得加括号）。
• 整除判断：a % b == 0 表示 a 能被 b 整除。
• 同余基础（5.3 详讲）：(a + b) % p、(a * b) % p 可以拆开取模（接 0.2）。
• about 因子：d 是 n 的因子，则 n/d 也是因子，因子成对出现（求因子只需枚举到 √n，接 5.2）。

五、本节速记卡

• GCD：__gcd(a, b)（内置，最方便），原理辗转相除 gcd(a,b)=gcd(b,a%b)。
• LCM：a / __gcd(a, b) * b，先除后乘防溢出，用 long long。
• 快速幂（必背）：求 a^b mod p，O(log b)。迭代版：

while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }

每步取模 + long long。数论第一高频模板。

• 快速乘：两个大数相乘取模防溢出。实战优先用 (__int128)a*b%p。
• 应用：快速幂用于大数幂取模、求逆元（5.3）、矩阵快速幂。

这一节是数论的"工具箱"。GCD/LCM 简单直接，快速幂是绝对的核心（务必背到能默写，后面好几个知识点都依赖它）。快速乘和 __int128 是处理大数溢出的兜底手段。

这些工具本身不难，关键是记住模板、理解原理。它们会在后面的素数、逆元、组合数里反复作为零件出现。

下一节 5.2 素数——筛法（埃氏筛、线性筛）求素数、分解质因数。素数是铜牌很常用的数论内容，筛法模板固定，分解质因数也是高频技巧。

配套练习题

好，给你 5 道数论基础题，GCD/LCM、快速幂模板、大数取模。这些是数论的基本零件，把模板练到能默写很重要。

老规矩：先自己写，重点想清楚"用哪个工具、防溢出（先除后乘/long long/取模）",再展开对照。

第 1 题：最大公约数与最小公倍数（GCD/LCM 模板）

题意：给两个正整数 a 和 b，求它们的最大公约数和最小公倍数。

输入样例
12 18

输出样例
6 36

（gcd(12,18)=6，lcm(12,18)=12×18/6=36）

考点：GCD/LCM 模板。__gcd 求最大公约数，a/gcd*b 求最小公倍数（先除后乘防溢出，long long）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = __gcd(a, b);
    long long l = a / g * b;        // 先除后乘防溢出！
    cout << g << " " << l << "\n";
    return 0;
}

第 2 题：分数化简（GCD 应用）

题意：给一个分数 a/b（a、b 为正整数），化简成最简形式（分子分母互质），输出化简后的分子和分母。

输入样例
12 18

输出样例
2 3

（12/18 = 2/3，同除以gcd=6）

考点：GCD 约分。分子分母同除以它们的 gcd。练习 GCD 的经典应用——约分。

提示：求 g = gcd(a, b)，输出 a/g 和 b/g。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    long long g = __gcd(a, b);
    cout << a / g << " " << b / g << "\n";   // 同除以gcd
    return 0;
}

第 3 题：快速幂（模板裸题 —— 必背）

题意：求 a^b mod p，其中 a、b、p 都是正整数，b 可能很大（到 10⁹）。

输入样例
2 10 1000

输出样例
24

（2¹⁰ = 1024，mod 1000 = 24）

输入样例
3 100 1000000007

输出样例
... (一个大数对1e9+7取模的结果)

考点：快速幂模板。迭代版 while(b){if(b&1)res=res*a%p; a=a*a%p; b>>=1;}。每步取模 + long long。这是数论第一高频模板，必须背到能默写。

#include <bits/stdc++.h>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;                    // 先取模
    while (b > 0) {
        if (b & 1) res = res * a % p;   // 当前位是1，累乘
        a = a * a % p;                   // a自乘
        b >>= 1;                         // 处理下一位
    }
    return res;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    cout << qpow(a, b, p) << "\n";
    return 0;
}

第 4 题：多个数的最大公约数（GCD 推广）

题意：给 n 个正整数，求它们所有数的最大公约数。

输入样例
4
12 18 24 30

输出样例
6

（gcd(12,18,24,30)=6）

考点：多个数的 GCD。依次求 gcd(gcd(gcd(a1,a2),a3),...)。练习"多个数的 gcd 用依次累积"。

提示：g = a[0]，然后 for i: g = __gcd(g, a[i])。LCM 同理可推广（但多个数的LCM容易溢出，注意）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long g = 0;               // gcd(0,x)=x，所以初始0也行
    for (int i = 0; i < n; i++) {
        long long x; cin >> x;
        g = __gcd(g, x);           // 依次累积
    }
    cout << g << "\n";
    return 0;
}

第 5 题：幂塔取模（快速幂应用 —— 有难度）

题意：求 (a^b + c^d) mod p，其中 a、b、c、d 可能都很大，p 是质数。

输入样例
2 10 3 5 1000

输出样例
267

（2¹⁰=1024, 3⁵=243, (1024+243) mod 1000 = 1267 mod 1000 = 267）

考点：快速幂的组合应用 + 取模加法。分别用快速幂求 a^b mod p 和 c^d mod p，再相加取模。练习"快速幂作为零件 + 取模运算的组合"。

提示：① 写一个快速幂函数；② 分别算 qpow(a,b,p) 和 qpow(c,d,p)；③ 结果 (x + y) % p（接 0.2 取模加法）。注意两个幂相加后再取模。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, b, c, d, p;
    cin >> a >> b >> c >> d >> p;
    long long x = qpow(a, b, p);
    long long y = qpow(c, d, p);
    cout << (x + y) % p << "\n";    // 取模加法
    return 0;
}

考点回顾：

1. GCD/LCM —— 模板（先除后乘）
2. 分数化简 —— GCD约分
3. 快速幂 —— 模板（必背）
4. 多个数GCD —— 依次累积
5. 幂塔取模 —— 快速幂组合应用

最该吃透的认知：

• 快速幂（第3题）是数论第一高频模板，必须背到能默写。迭代版 while(b){if(b&1)res=res*a%p; a=a*a%p; b>>=1;} 闭着眼睛能敲。它在后面求逆元、组合数取模反复出现。
• LCM 的先除后乘（第1题）——a/gcd*b 而非 a*b/gcd，防中间溢出。这是 LCM 的经典坑。
• GCD 的应用（第2、4题）——约分、判互质、多数gcd，都是 __gcd 的直接运用。
• 快速幂作零件（第5题）——数论题里快速幂常常是更大计算的一部分，配合取模运算。

核心记忆——数论基础三件套：

__gcd(a, b)                    // 最大公约数
a / __gcd(a,b) * b             // 最小公倍数（先除后乘）
qpow(a, b, p)                  // 快速幂 a^b mod p（背模板）

把快速幂模板练到肌肉记忆，GCD/LCM 会用，数论基础就过关了。

先建立认知：

素数（质数）= 只能被 1 和自身整除的、大于 1 的整数（如 2, 3, 5, 7, 11...）。1 不是素数，2 是最小的素数（也是唯一的偶素数）。
素数题主要三类：①判断一个数是不是素数 ②批量求出一定范围内所有素数（筛法）③把一个数分解成质因数的乘积。

一、判断单个数是否为素数（试除法）

朴素试除法

判断 n 是否素数：看它能不能被 2 到 n-1 中的某个数整除。但只需试到 √n 即可——因为因子成对出现，如果 n 有大于 √n 的因子，必然也有小于 √n 的对应因子。

bool isPrime(int n) {
    if (n < 2) return false;          // 0、1 不是素数
    for (int i = 2; i * i <= n; i++)  // 只试到 √n（i*i <= n 等价于 i <= √n）
        if (n % i == 0) return false; // 能被整除，不是素数
    return true;
}

关键点：

• i * i <= n 而不是 i <= sqrt(n)：用 i*i <= n 避免浮点误差（接 0.3，sqrt 是浮点运算可能不准），且更快。
• 复杂度 O(√n)：单次判断很快，n=10⁹ 也只要约 3 万次。

判断单个数用试除法，只试到 √n。这是判断素数的基本方法，i*i <= n 这个写法要记住（既快又避免浮点坑）。

二、批量筛素数（筛法，重点）

当需要求出 1~n 范围内所有素数时，逐个用试除法判断太慢（O(n√n)）。筛法能在 O(n log log n) 或 O(n) 内筛出所有素数。

埃氏筛（埃拉托斯特尼筛法，最常用）

核心思想：从小到大，每找到一个素数，就把它的所有倍数都标记为合数（非素数）。剩下没被标记的就是素数。

const int N = 1e6 + 5;
bool isComposite[N];   // isComposite[i] = true 表示 i 是合数

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {              // i 是素数
            for (int j = i * 2; j <= n; j += i)   // 把 i 的倍数标记为合数
                isComposite[j] = true;
        }
    }
    // 此时 isComposite[i] == false 的 i（且 i>=2）都是素数
}

理解：

• 从 2 开始，2 是素数，把 4、6、8... 标记为合数。
• 3 没被标记，是素数，把 6、9、12... 标记。
• 4 已被标记（合数），跳过。
• 5 没被标记，是素数，标记 10、15...
• 以此类推，每个合数都会被它的某个素因子标记掉，剩下的就是素数。

收集素数：

vector<int> primes;
for (int i = 2; i <= n; i++)
    if (!isComposite[i]) primes.push_back(i);   // 收集所有素数

埃氏筛是最常用的筛法，代码简单。复杂度 O(n log log n)，近似线性。一次筛出 1~n 所有素数，后面 O(1) 查询某个数是否素数（看 isComposite）。需要多次判断素数、或需要一批素数时，用筛法而非逐个试除。

优化：从 i*i 开始标记

埃氏筛有个小优化——标记 i 的倍数时，从 i*i 开始（因为比 i*i 小的倍数，如 i*2, i*3，已经被更小的素数标记过了）：

for (int j = i * i; j <= n; j += i)   // 从 i*i 开始（注意 i*i 可能溢出，大n时用 long long）
    isComposite[j] = true;

这个优化能稍微减少重复标记。注意 i*i 在 n 大时可能溢出 int（接 0.2），可以写成 (long long)i*i 或判断一下。铜牌阶段从 i*2 开始也能过，从 i*i 是锦上添花。

线性筛（欧拉筛，了解）

埃氏筛会重复标记（一个合数被多个素因子标记多次）。线性筛保证每个合数只被它的最小质因子标记一次，达到严格 O(n)。代码稍复杂：

const int N = 1e6 + 5;
bool isComposite[N];
vector<int> primes;

void linearSieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) primes.push_back(i);   // i 是素数
        for (int p : primes) {
            if (i * p > n) break;
            isComposite[i * p] = true;              // 标记 i*p 为合数
            if (i % p == 0) break;                  // 关键：保证最小质因子标记
        }
    }
}

线性筛 O(n)，比埃氏筛理论更优，但代码复杂些。铜牌阶段埃氏筛通常够用（n=10⁶ 时埃氏筛也很快），线性筛在 n 很大（10⁷以上）或需要顺便求一些积性函数时才必要。先掌握埃氏筛，线性筛了解。

三、分解质因数（高频技巧）

解决什么问题

把一个数 n 写成质因数的乘积，如 60 = 2² × 3 × 5。求出每个质因子和它的次数。

试除法分解

从最小的质数 2 开始，不断除以当前因子，直到除不尽换下一个：

void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {   // 试除到 √n
        while (n % i == 0) {             // i 是因子，一直除
            cout << i << " ";            // 输出质因子 i（可统计次数）
            n /= i;
        }
    }
    if (n > 1) cout << n << " ";         // 剩下的 n（如果>1）是一个大质因子
}

关键点（重要）：

• 试除到 √n 即可：和判断素数同理。
• if (n > 1) 那一步是关键：循环只试到 √n，如果除完后 n 还大于 1，说明剩下的 n 本身是一个大于 √原n 的质因子（最多只有一个这样的因子）。这一步容易漏，漏了会丢失大质因子。

举例：分解 60。

• i=2：60/2=30, 30/2=15，得两个 2，n=15。
• i=3：15/3=5，得一个 3，n=5。
• i=4：4×4=16>5，循环结束。
• n=5>1，输出 5（这是大质因子）。
• 结果：2 2 3 5，即 60 = 2²×3×5。

统计质因子及次数

void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }   // 数 i 的次数
            cout << i << "^" << cnt << " ";          // 输出 i 的 cnt 次方
        }
    }
    if (n > 1) cout << n << "^1";   // 剩余大质因子，次数1
}

分解质因数是高频技巧，核心是"从小到大试除，除尽换下一个，最后别忘剩余的大质因子"。if (n > 1) 处理大质因子那一步是最容易漏的坑，务必记住。

四、素数相关的常见应用

• 判断素数：单个用试除法，多个用筛法预处理。
• 求一定范围素数个数/列表：筛法。
• 分解质因数：求约数个数、约数和、最大公约数等的基础。
• 约数个数：如果 n = p1^a1 × p2^a2 × ...，则约数个数 = (a1+1)(a2+1)...（每个质因子的次数+1再相乘）。这是分解质因数的经典应用。

// 求 n 的约数个数（基于分解质因数）
int countDivisors(int n) {
    int cnt = 1;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int e = 0;
            while (n % i == 0) { n /= i; e++; }
            cnt *= (e + 1);          // 每个质因子贡献 (次数+1)
        }
    }
    if (n > 1) cnt *= 2;             // 剩余大质因子，次数1，贡献2
    return cnt;
}

五、本节速记卡

• 判断单个素数：试除法，只试到 √n，写 i*i <= n（避免浮点，更快）。O(√n)。
• 批量筛素数（重点）：
• 埃氏筛（最常用）：每个素数标记其所有倍数为合数。O(n log log n)。for i: if(!合数) for j=i*2 to n step i: 标记j。
• 线性筛（了解）：每个合数只被最小质因子标记，严格 O(n)，代码复杂。
• 分解质因数：从 2 试除到 √n，除尽换下一个，最后 if(n>1) 处理大质因子（易漏的坑）。
• 应用：约数个数 = 各质因子(次数+1)的乘积。
• 选择：单次判断用试除法；多次/批量用筛法预处理。

素数是数论里实用且常考的一块。核心三个工具：试除法判素数（i*i<=n）、埃氏筛（批量筛素数）、分解质因数（别漏大质因子）。把这三个模板记住，素数题基本能套。

最关键的两点：① 埃氏筛模板（需要一批素数或多次判断时用）；② 分解质因数的 if(n>1) 那步（处理大质因子，最容易漏）。

下一节 5.3 同余与逆元——费马小定理、扩展欧几里得、模意义下的除法（逆元）。它会用到你刚复习的快速幂（费马小定理求逆元）。这是组合数取模（5.4）的前置，稍微抽象一点，但模板固定。

配套练习题

好，给你 5 道素数题，判素数、埃氏筛、分解质因数、约数个数。素数是常考内容，把三个核心工具（试除、筛法、分解）练熟很值。

老规矩：先自己写，重点想清楚"单个判断还是批量、试除到√n、分解别漏大质因子",再展开对照。

第 1 题：判断素数（试除法 —— 模板）

题意：给 q 个数，对每个判断是否为素数，是输出 YES，否则 NO。每个数 ≤ 10⁹。

输入样例
4
2
4
17
1

输出样例
YES
NO
YES
NO

（2是素数；4=2×2不是；17是素数；1不是素数）

考点：试除法判素数。只试到 √n（i*i <= n），注意 1 和 0 不是素数。因为数大（10⁹）且只有几个，用试除法而非筛法。

#include <bits/stdc++.h>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;          // 0、1不是素数
    for (long long i = 2; i * i <= n; i++)   // 只试到√n
        if (n % i == 0) return false;
    return true;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        long long n;
        cin >> n;
        cout << (isPrime(n) ? "YES" : "NO") << "\n";
    }
    return 0;
}

第 2 题：区间素数个数（埃氏筛 —— 模板）

题意：求 1 到 n 之间（含 n）有多少个素数。n ≤ 10⁶。

输入样例
20

输出样例
8

（2,3,5,7,11,13,17,19 共8个素数）

考点：埃氏筛。n 较大（10⁶）且要数素数个数，用筛法一次筛出所有素数再统计。练习埃氏筛模板。

提示：埃氏筛标记所有合数，最后统计 !isComposite[i] 的个数（i 从2到n）。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
bool isComposite[N];

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i])                  // i是素数
            for (int j = i * 2; j <= n; j += i)   // 标记倍数
                isComposite[j] = true;
    }
    int cnt = 0;
    for (int i = 2; i <= n; i++)
        if (!isComposite[i]) cnt++;
    cout << cnt << "\n";
    return 0;
}

第 3 题：分解质因数（试除分解 —— 模板）

题意：把一个正整数 n 分解成质因数的乘积，按质因子从小到大输出，格式为 质因子^次数。n ≤ 10⁹。

输入样例
60

输出样例
2^2 3^1 5^1

（60 = 2²×3×5）

输入样例
17

输出样例
17^1

（17本身是质数）

考点：分解质因数模板。从2试除到√n，统计每个质因子次数，最后 if(n>1) 处理大质因子（最容易漏）。

提示：① 从 i=2 试除到 i*i<=n；② 每个因子统计次数（while除尽）；③ 循环后若 n>1，剩余的 n 是大质因子，次数为1。第二个样例17就是考这个——17>√17，循环试不到，靠最后的 if(n>1) 输出。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    bool first = true;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }   // 数次数
            if (!first) cout << " ";
            cout << i << "^" << cnt;
            first = false;
        }
    }
    if (n > 1) {                       // 剩余大质因子！
        if (!first) cout << " ";
        cout << n << "^1";
    }
    cout << "\n";
    return 0;
}

第 4 题：约数个数（分解质因数应用 —— 重要）

题意：求正整数 n 的约数（因子）个数。n ≤ 10⁹。

输入样例
12

输出样例
6

（12的约数：1,2,3,4,6,12，共6个）

考点：约数个数 = 各质因子(次数+1)的乘积。分解质因数后，把每个质因子的"次数+1"相乘。练习"分解质因数 → 约数个数公式"这个经典应用。

提示：① 分解质因数，记每个质因子的次数 e；② 约数个数 = Π(e_i + 1)（每个质因子贡献次数+1）；③ 别忘 if(n>1) 的大质因子也贡献 (1+1)=2。例：12=2²×3¹，约数个数=(2+1)×(1+1)=6。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long cnt = 1;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int e = 0;
            while (n % i == 0) { n /= i; e++; }
            cnt *= (e + 1);            // 每个质因子贡献(次数+1)
        }
    }
    if (n > 1) cnt *= 2;               // 大质因子，次数1，贡献(1+1)=2
    cout << cnt << "\n";
    return 0;
}

第 5 题：哥德巴赫分解（筛法应用 —— 有难度）

题意：给一个大于2的偶数 n（n ≤ 10⁶），把它表示成两个素数之和（哥德巴赫猜想：任何大于2的偶数都能表示成两个素数之和）。输出任意一组满足条件的素数对 p q（p ≤ q）。

输入样例
10

输出样例
3 7

（10 = 3+7，3和7都是素数；也可以是5+5，输出任意一组）

考点：埃氏筛 + 枚举。先筛出所有素数，然后枚举较小的素数 p，看 n-p 是否也是素数。练习"筛法预处理 + 枚举找素数对"。

提示：① 先用埃氏筛预处理 1~n 的素数；② 枚举 p 从2开始，如果 p 是素数且 n-p 也是素数，输出 p 和 n-p；③ 找到一组就停。用 isComposite 数组 O(1) 判断素数。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
bool isComposite[N];

int main() {
    int n;
    cin >> n;
    // 埃氏筛预处理
    for (int i = 2; i < N; i++)
        if (!isComposite[i])
            for (int j = i * 2; j < N; j += i)
                isComposite[j] = true;

    // 枚举较小素数p，看n-p是否也是素数
    for (int p = 2; p <= n / 2; p++) {
        if (!isComposite[p] && !isComposite[n - p]) {   // p和n-p都是素数
            cout << p << " " << n - p << "\n";
            break;                     // 找到一组就停
        }
    }
    return 0;
}

考点回顾：

1. 判素数 —— 试除法（√n）
2. 区间素数个数 —— 埃氏筛
3. 分解质因数 —— 试除分解（大质因子）
4. 约数个数 —— 分解的应用
5. 哥德巴赫分解 —— 筛法+枚举

最该吃透的认知：

• 三个核心工具——试除法判单个素数（第1题）、埃氏筛批量筛素数（第2、5题）、分解质因数（第3、4题）。这三个模板覆盖了素数题的大部分。
• 何时用试除、何时用筛法——单个/少量判断且数大用试除（第1题，10⁹试除很快）；需要一批素数或多次判断用筛法预处理（第2、5题，筛一次后O(1)查询）。
• 分解质因数的 if(n>1)（第3、4题）——处理大于√n的大质因子，最容易漏的坑。循环只试到√n，剩下的n若>1必是一个大质因子。
• 约数个数公式（第4题）——Π(质因子次数+1)，是分解质因数最经典的应用，要记住。

核心记忆——素数三件套：

// 1.判单个：试除到√n
for(i=2; i*i<=n; i++) if(n%i==0) 不是素数;
// 2.批量筛：埃氏筛
for(i=2;i<=n;i++) if(!合数) for(j=i*2;j<=n;j+=i) 标记合数;
// 3.分解：试除+大质因子
for(i=2;i*i<=n;i++) while(n%i==0) n/=i,记录i; if(n>1) 记录n;

把这三个练熟，素数题就稳了。

先点破这一节要解决的核心痛点：

取模运算里，加、减、乘都能直接拆（接 0.2）：(a+b)%p、(a*b)%p 都对。但除法不行！(a/b)%p ≠ (a%p)/(b%p)。
那模意义下怎么算 (a/b) mod p？答案是——用"逆元"把除法变成乘法。这就是本节的核心。

一、同余的基本概念（快速过）

同余：如果 a 和 b 除以 m 的余数相同，就说 a 和 b 模 m 同余，记作 a ≡ b (mod m)。

同余的基本运算规则（你在 0.2 已经用过）：

• 加：(a + b) mod m
• 减：((a - b) mod m + m) mod m（加 m 防负数，接 0.2）
• 乘：(a * b) mod m

这三个都能"边算边取模"。唯独除法不能直接取模——这就是为什么需要逆元。

二、为什么除法不能直接取模（理解动机）

举个例子：算 (6 / 2) mod 5。

• 正确答案：6/2 = 3，3 mod 5 = 3。
• 错误做法：(6 mod 5) / (2 mod 5) = 1 / 2，这在整数里是 0，错了。

问题：取模破坏了除法。当题目要求"a/b 的结果对 p 取模"，而 a、b 本身是大数（已经取过模），你没法直接除。

解决思路：把"除以 b"转化成"乘以 b 的逆元"。逆元就是模意义下 b 的"倒数"。

三、逆元的定义

逆元：在模 p 意义下，如果 b × x ≡ 1 (mod p)，那么 x 就是 b 的逆元，记作 b⁻¹。

逆元的作用：模意义下的除法 = 乘以逆元：

(a / b) mod p = (a × b⁻¹) mod p

类比：普通数学里 a / b = a × (1/b)，1/b 是 b 的倒数。模意义下，b⁻¹ 就是 b 的"倒数"（满足 b × b⁻¹ ≡ 1）。求出逆元，除法就变成乘法了。

逆元存在的条件：b 和 p 互质（gcd(b,p)=1）。当 p 是质数且 b 不是 p 的倍数时，逆元一定存在——而竞赛里模数 p 通常是质数（如 10⁹+7），所以这个条件一般满足。

四、求逆元方法 1：费马小定理（最常用，配快速幂）

费马小定理

当 p 是质数，且 a 不是 p 的倍数时：a^(p-1) ≡ 1 (mod p)。

从这个定理推逆元：把 a^(p-1) ≡ 1 写成 a × a^(p-2) ≡ 1，对比逆元定义 a × a⁻¹ ≡ 1，立刻得到：

a 的逆元 = a^(p-2) mod p（当 p 是质数）。

而 a^(p-2) mod p 正好用快速幂求！（接 1.6 / 5.1）

long long qpow(long long a, long long b, long long p) {   // 快速幂（复习）
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 求 a 在模 p 下的逆元（p 必须是质数）
long long inverse(long long a, long long p) {
    return qpow(a, p - 2, p);    // 费马小定理：a^(p-2) 就是逆元
}

用逆元做除法：

// 计算 (a / b) mod p（p 是质数）
long long divmod(long long a, long long b, long long p) {
    return a % p * inverse(b, p) % p;   // a × b⁻¹
}

费马小定理求逆元是最常用的方法，因为竞赛模数通常是质数（10⁹+7、998244353 都是质数）。记住：逆元 = 快速幂算 a^(p-2)。 这就是"模意义下除法"的标准做法，组合数取模（5.4）的核心工具。

五、求逆元方法 2：扩展欧几里得（了解，模数非质数时用）

当 p 不是质数（但 gcd(a,p)=1）时，费马小定理不适用，要用扩展欧几里得算法求逆元。

扩展欧几里得（exgcd）

普通欧几里得求 gcd（5.1）。扩展欧几里得在求 gcd 的同时，求出满足 a×x + b×y = gcd(a,b) 的一组 x, y。

// 返回 gcd(a,b)，同时求出 x, y 使 a*x + b*y = gcd(a,b)
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);   // 注意 x、y 交换
    y -= (a / b) * x;
    return g;
}

// 用 exgcd 求 a 在模 p 下的逆元
int inverse(int a, int p) {
    int x, y;
    exgcd(a, p, x, y);          // 求 a*x + p*y = 1
    return (x % p + p) % p;     // x 就是逆元（调整到正数）
}

原理：求 a×x + p×y = 1，那么 a×x ≡ 1 (mod p)，所以 x 就是 a 的逆元。

扩展欧几里得求逆元，不要求 p 是质数（只要 gcd(a,p)=1）。铜牌阶段，模数几乎都是质数，所以优先用费马小定理（更简单）。扩展欧几里得了解即可，遇到非质数模数再用。它还能解线性同余方程，是更通用的工具。

六、两种求逆元方法对比

记忆：模数是质数 → 费马小定理 + 快速幂（首选）；模数非质数 → 扩展欧几里得。 竞赛里 99% 用费马小定理。

七、逆元的典型应用

逆元最主要的用途是模意义下的除法，具体场景：

• 组合数取模（5.4 重点）：C(n,m) = n! / (m!(n-m)!)，分母的阶乘要用逆元。
• 求分数的模：(a/b) mod p，把除法变乘逆元。
• 概率/期望取模：概率是分数，取模时用逆元。
• 预处理阶乘逆元：批量求组合数时，预处理 1!~n! 的逆元（线性递推优化）。

八、本节速记卡

• 核心痛点：模意义下加减乘能直接拆，除法不能——要用逆元把除法变乘法。
• 逆元定义：b × b⁻¹ ≡ 1 (mod p)，则 (a/b) mod p = a × b⁻¹ mod p。
• 求逆元（费马小定理，首选）：p 是质数时，逆元 = a^(p-2) mod p，用快速幂算。

long long inv = qpow(a, p - 2, p);   // 必背

• 求逆元（扩展欧几里得，备用）：p 非质数时，exgcd 求 ax+py=1，x 是逆元。
• 存在条件：gcd(a,p)=1（p 质数时只要 a 不是 p 的倍数）。
• 应用：组合数取模、分数取模、概率期望取模。
• 选择：模数质数用费马小定理（99%情况），非质数用扩展欧几里得。

这一节的核心就一件事：模意义下的除法，用逆元（变成乘法）。 而求逆元的主力方法是费马小定理 + 快速幂（a^(p-2)）——你已经会快速幂了，所以这其实就是快速幂的一个应用。记住"逆元 = 快速幂算 a⁽ᵖ⁻²⁾"这个结论，就掌握了铜牌需要的逆元知识。

它本身可能用得不算特别频繁，但是组合数取模的必备前置——下一节就要用它。

下一节 5.4 组合数学——排列组合、组合数计算、组合数取模（用到逆元）。计数类题目经常需要算组合数 C(n,m)，而大数取模就要用逆元。这是数论部分的最后一个核心内容。

配套练习题

好，给你 4 道同余/逆元题，费马小定理求逆元、模意义下除法、分数取模。逆元的核心就是"除法变乘法"，把费马小定理求逆元的套路练熟即可。

老规矩：先自己写，重点想清楚"哪里有除法、怎么用逆元替代、模数是不是质数",再展开对照。

第 1 题：求逆元（费马小定理 —— 模板）

题意：给一个正整数 a 和质数 p，求 a 在模 p 意义下的逆元（即满足 a×x ≡ 1 (mod p) 的 x，输出 [0, p) 范围内的 x）。

输入样例
3 7

输出样例
5

（3×5 = 15 = 14+1 ≡ 1 (mod 7)，所以 3 的逆元是 5）

考点：费马小定理求逆元。逆元 = a^(p-2) mod p，用快速幂算。这是逆元的核心模板。

#include <bits/stdc++.h>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, p;
    cin >> a >> p;
    cout << qpow(a, p - 2, p) << "\n";   // 费马小定理：逆元=a^(p-2)
    return 0;
}

第 2 题：模意义下的除法（逆元应用）

题意：给三个数 a、b、p（p 是质数），求 (a / b) mod p（保证 b 不是 p 的倍数）。注意 a、b 可能很大。

输入样例
10 2 7

输出样例
5

（10/2 = 5，5 mod 7 = 5。验证：用逆元 10 × 2⁻¹ mod 7，2的逆元是4，10×4=40 mod 7 = 40-35=5 ✓）

考点：模意义下除法 = 乘以逆元。(a/b) mod p = a × inverse(b) mod p。练习"把除法转成乘逆元"。

提示：① 求 b 的逆元 qpow(b, p-2, p)；② 结果 = a % p * 逆元 % p。注意 a 先取模，乘法用 long long（接 0.2）。

#include <bits/stdc++.h>
using namespace std;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    long long inv = qpow(b, p - 2, p);     // b的逆元
    cout << a % p * inv % p << "\n";        // a × b⁻¹
    return 0;
}

第 3 题：组合数取模（逆元应用 —— 重要，5.4 预热）

题意：给 n 和 m（n ≥ m），求组合数 C(n, m) mod (10⁹+7)。即从 n 个中选 m 个的方案数，对 10⁹+7 取模。n, m ≤ 10⁶。

输入样例
5 2

输出样例
10

（C(5,2) = 5!/(2!×3!) = 10）

考点：组合数取模。C(n,m) = n! / (m! × (n-m)!)，分母的阶乘要用逆元。预处理阶乘，分母用逆元。这是逆元最重要的应用，也是 5.4 的核心预热。

提示：① 预处理阶乘 fact[i] = i! mod p；② C(n,m) = fact[n] × inverse(fact[m]) × inverse(fact[n-m]) % p；③ 逆元用费马小定理 qpow(x, p-2, p)。注意全程取模 + long long。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N];

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

long long inverse(long long x) { return qpow(x, MOD - 2, MOD); }

int main() {
    int n, m;
    cin >> n >> m;
    // 预处理阶乘
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    // C(n,m) = n! / (m! × (n-m)!) = fact[n] × inv(fact[m]) × inv(fact[n-m])
    long long ans = fact[n] * inverse(fact[m]) % MOD * inverse(fact[n-m]) % MOD;
    cout << ans << "\n";
    return 0;
}

第 4 题：分数求和取模（逆元综合 —— 有难度）

题意：计算 (1/1 + 1/2 + 1/3 + ... + 1/n) mod (10⁹+7)。即前 n 项调和级数的和，每一项是分数，结果对质数取模。n ≤ 10⁶。

输入样例
3

输出样例
... (1 + 1/2 + 1/3 = 11/6，在模意义下的值)

（1/1 + 1/2 + 1/3 = 11/6。模意义下：1×1⁻¹ + 1×2⁻¹ + 1×3⁻¹，即 1的逆元+2的逆元+3的逆元，相加取模）

考点：每一项 1/i 在模意义下是 i 的逆元。把所有逆元相加取模。练习"分数和 = 逆元和"。

提示：① 每项 1/i mod p = inverse(i, p) = qpow(i, p-2, p)；② 累加所有 inverse(i)，每步取模；③ 答案 = Σ inverse(i) mod p。注意 n=10⁶ 时要算 10⁶ 次快速幂，每次 O(log p)，总共约 10⁶×30 = 3×10⁷ 可以接受。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long qpow(long long a, long long b, long long p) {
    long long res = 1;
    a %= p;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + qpow(i, MOD - 2, MOD)) % MOD;   // 每项1/i=i的逆元，累加
    }
    cout << ans << "\n";
    return 0;
}

考点回顾：

1. 求逆元 —— 费马小定理（模板）
2. 模意义除法 —— 乘逆元
3. 组合数取模 —— 逆元应用（重要）
4. 分数求和 —— 逆元和

最该吃透的认知：

• 费马小定理求逆元（第1题）——逆元 = a^(p-2) mod p（p质数），用快速幂算。这是核心结论，记死。逆元就是快速幂的应用。
• 除法变乘逆元（第2题）——模意义下 (a/b) mod p = a × b⁻¹ mod p。所有"模意义下的除法"都这么处理。
• 组合数取模（第3题）——C(n,m)=n!/(m!(n-m)!)，分母阶乘用逆元。这是逆元最重要的应用，也是5.4的核心。预处理阶乘 + 逆元是标准套路。
• 分数运算全靠逆元（第4题）——任何模意义下的分数（1/i、a/b、概率期望）都转成逆元乘法。

核心记忆——逆元就一个结论：

inverse(a) = qpow(a, p-2, p)    // p是质数，费马小定理
// 模意义下除法：(a/b)%p = a * inverse(b) % p

记住这个 + 会快速幂，逆元就够铜牌用了。

先抓住本质：

组合数学 = 研究"计数"的学问——有多少种排列、有多少种选法、有多少种方案。
核心是两个概念：排列（讲顺序）和组合（不讲顺序），以及它们的计算和取模。

一、两个核心概念：排列与组合

排列（讲顺序）

从 n 个不同元素中，取出 m 个，并排成一个顺序，方案数记作 A(n,m) 或 P(n,m)：

A(n,m) = n × (n-1) × (n-2) × ... × (n-m+1) = n! / (n-m)!

理解：第一个位置有 n 种选择，第二个有 n-1 种，...，第 m 个有 n-m+1 种，相乘。

例：从 5 个人选 3 个排成一队 = A(5,3) = 5×4×3 = 60。

组合（不讲顺序）

从 n 个不同元素中，取出 m 个（不排顺序，只看选了哪些），方案数记作 C(n,m)：

C(n,m) = A(n,m) / m! = n! / (m! × (n-m)!)

理解：组合 = 排列 ÷ m!（因为选出的 m 个元素，它们之间的 m! 种排列在组合里算同一种，要除掉）。

例：从 5 个人选 3 个（不排顺序）= C(5,3) = 5!/(3!×2!) = 10。

排列 vs 组合的区别就是"讲不讲顺序"：排队、密码（顺序重要）用排列；选小组、选物品（只看选谁）用组合。组合 = 排列 / m!。这个区别和你在 2.2 回溯学的"排列用 used、组合用 start"一脉相承。

二、组合数的重要性质（记几个）

组合数有些常用性质，能简化计算：

1. 对称性：C(n,m) = C(n,n-m)（选 m 个 = 选剩下的 n-m 个不选哪些）。
2. 边界：C(n,0) = C(n,n) = 1（选 0 个或全选，都只有 1 种）。
3. 递推（杨辉三角）：C(n,m) = C(n-1,m-1) + C(n-1,m)（第 n 个元素选或不选）。

性质 3（杨辉三角递推）很重要——它对应"第 n 个元素：选它（C(n-1,m-1)）或不选它（C(n-1,m)）"，正是组合的"选或不选"思想（呼应 DP）。这给了一种不用除法算组合数的方法（见下文）。

三、计算组合数的方法（按场景选）

计算 C(n,m) 有几种方法，根据数据范围和是否取模选择：

方法 1：杨辉三角递推（n 小，不超过几千）

用递推 C[n][m] = C[n-1][m-1] + C[n-1][m] 预处理出一个表。不用除法，天然适合取模：

const int N = 2005, MOD = 1e9 + 7;
long long C[N][N];

void initC(int n) {
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;                          // C(i,0)=1
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;   // 杨辉三角递推
    }
}
// 查询 C(n,m) 直接 C[n][m]

适用：n、m 都不大（n ≤ 几千，因为是 O(n²) 的表）。优点：无除法，取模简单，多次查询 O(1)。

方法 2：阶乘 + 逆元（n 大，需要取模）

当 n 很大（10⁶ 级），用阶乘公式 C(n,m) = n! / (m!(n-m)!)，分母的阶乘用逆元（接 5.3）：

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N], inv_fact[N];

long long qpow(long long a, long long b, long long p) {   // 快速幂
    long long res = 1; a %= p;
    while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }
    return res;
}

void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;   // 阶乘
    inv_fact[n] = qpow(fact[n], MOD - 2, MOD);                    // 最大阶乘的逆元
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;   // 逆元递推（优化）
}

long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;   // 公式
}

适用：n 很大（10⁶），需要取模。预处理阶乘和阶乘逆元后，每次查询 O(1)。

逆元递推优化（重要技巧）：不用对每个阶乘单独求逆元（那样 n 次快速幂太慢），而是先求最大阶乘 fact[n] 的逆元，然后倒推：inv_fact[i] = inv_fact[i+1] × (i+1)。这样只用一次快速幂，其余 O(1) 递推。这是批量组合数取模的标准优化。

方法 3：直接乘除（单个组合数，m 小）

如果只算一个 C(n,m) 且 m 不大，可以直接按定义算（不取模时）：

long long C(int n, int m) {
    if (m > n - m) m = n - m;        // 利用对称性，取较小的m
    long long res = 1;
    for (int i = 0; i < m; i++)
        res = res * (n - i) / (i + 1);   // 边乘边除
    return res;
}

注意：这种不取模、可能溢出，只适合结果不大的情况。取模时不能这么直接除（要用逆元）。

四、怎么选计算方法（决策）

记忆：n 小用杨辉三角，n 大用阶乘逆元。 取模时这两种是主力（都避免了直接除法的问题——杨辉三角用加法，阶乘用逆元）。

五、常见的计数模型（积累）

组合数学题常涉及这些经典模型：

模型 1：基本排列组合

直接套 A(n,m) 或 C(n,m)。判断讲不讲顺序选排列还是组合。

模型 2：隔板法（了解）

把 n 个相同物品分给 k 个人（每人至少 1 个）的方案数 = C(n-1, k-1)（在 n 个物品的 n-1 个空隙里插 k-1 个隔板）。变体：每人可以 0 个，方案数 C(n+k-1, k-1)。

模型 3：组合恒等式

如 C(n,0)+C(n,1)+...+C(n,n) = 2ⁿ（所有子集数，呼应 2.2 子集）。这类恒等式偶尔用到。

模型 4：路径计数

从 (0,0) 走到 (m,n)，只能向右/向上，方案数 = C(m+n, m)（在 m+n 步里选 m 步向右）。这其实就是 3.1 不同路径题的组合数解法！

教教练衔接coach

这些模型不用死记，理解"排列还是组合、要不要除掉重复"即可。路径计数和子集计数把组合数学和你学过的 DP/回溯联系了起来。

六、组合数学解题思维

1. 判断是计数问题：求"有多少种方案/排列/选法"。
2. 讲不讲顺序：讲顺序 → 排列 A；不讲 → 组合 C。
3. 套公式或模型：基本排列组合、隔板法、路径计数等。
4. 选计算方法：n 小用杨辉三角，n 大用阶乘逆元（取模时）。
5. 注意取模：组合数常常很大，要对质数取模，分母用逆元（接 5.3）。

七、本节速记卡

• 排列（讲顺序）：A(n,m) = n!/(n-m)!。
• 组合（不讲顺序）：C(n,m) = n!/(m!(n-m)!) = A(n,m)/m!。
• 区别：讲顺序用排列，不讲用组合；组合 = 排列/m!。
• 重要性质：对称 C(n,m)=C(n,n-m)；递推 C(n,m)=C(n-1,m-1)+C(n-1,m)（杨辉三角，选/不选）。
• 计算方法：
• 杨辉三角递推（n小≤几千，取模）：C[i][j]=C[i-1][j-1]+C[i-1][j]，无除法。
• 阶乘+逆元（n大10⁶，取模）：C=fact[n]×inv_fact[m]×inv_fact[n-m]，逆元递推优化。
• 经典模型：隔板法 C(n-1,k-1)、路径计数 C(m+n,m)、子集和 2ⁿ。
• 选择：n小杨辉三角，n大阶乘逆元。

组合数学是计数题的基础。核心是分清排列（顺序）vs 组合（不看顺序），以及会计算组合数取模（n 小杨辉三角、n 大阶乘逆元）。其中阶乘+逆元的方法把你前面学的快速幂、逆元串了起来，是计数题的常用工具。

铜牌阶段，组合数学出现频率中等——基本的排列组合、组合数取模会用到，复杂的组合恒等式较少。把"排列vs组合的判断"和"两种组合数计算方法"掌握就够用。

🎉 第五部分：数学 的核心内容基本完成！ 回顾数学之路：

• 5.1 数论基础（GCD/LCM、快速幂）
• 5.2 素数（筛法、分解质因数）
• 5.3 同余与逆元（费马小定理求逆元）
• 5.4 组合数学（排列组合、组合数取模）

（5.5 高精度你有基础，5.6 概率期望/矩阵快速幂/线性基是拓展，铜牌阶段可按需。）

至此，铜牌的核心知识体系已经基本搭建完成！ 让我们回顾你这段时间走过的完整路线：

• 第〇部分：实战工程技巧（I/O、调试、复杂度、比赛策略）
• 第一部分：基础算法与 STL
• 第二部分：搜索（DFS/BFS/回溯/剪枝/记忆化）
• 第三部分：动态规划（线性/背包/区间/树形）
• 第四部分：图论（并查集/最短路/MST/拓扑）
• 第五部分：数学（数论/素数/逆元/组合）

这就是冲击区域赛铜牌所需的完整知识框架。 你已经把它们一个一个攻下来了，从最初的零基础到现在，这是实打实的进步。

接下来的关键是 大量做题 + 打模拟赛，把这些知识真正变成"看到题就能用"的能力。还记得那套留着的模拟赛 #1 吗？现在是个好时机认真做一做，检验融会贯通的程度。

• 去认真做那套模拟赛 #1（强烈推荐，检验综合能力）
• 或者回头深入某个薄弱模块（比如 DP 还想多练）
• 或者进入剩下的章节（字符串 6.x、进阶数据结构 7.x，铜牌选学）

配套练习题

好，给你 5 道组合数学题，排列组合基础、组合数取模、隔板法、路径计数。组合数学的关键是"分清排列还是组合"+"会算组合数取模"。

老规矩：先自己写，重点想清楚"讲不讲顺序（排列还是组合）、套哪个公式/模型、n大小决定计算方法",再展开对照。

第 1 题：组合数取模（阶乘+逆元 —— 必会模板）

题意：给 q 次询问，每次给 n 和 m，求 C(n, m) mod (10⁹+7)。n, m ≤ 10⁶。

输入样例
3
5 2
10 3
6 6

输出样例
10
120
1

（C(5,2)=10，C(10,3)=120，C(6,6)=1）

考点：n 大（10⁶）+ 多次查询 → 阶乘+逆元预处理。预处理 fact 和 inv_fact，每次查询 O(1)。这是组合数取模的标准模板。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N], inv_fact[N];

long long qpow(long long a, long long b, long long p) {
    long long res = 1; a %= p;
    while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }
    return res;
}

void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD - 2, MOD);          // 最大阶乘逆元
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;       // 逆元递推
}

long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}

int main() {
    init(1000000);             // 预处理到10^6
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        cout << C(n, m) << "\n";
    }
    return 0;
}

第 2 题：杨辉三角（递推 —— 小范围组合数）

题意：输出杨辉三角的前 n 行。第 i 行第 j 个数是 C(i, j)（行列都从0开始）。每个数对 10⁹+7 取模。

输入样例
5

输出样例
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

考点：杨辉三角递推 C[i][j] = C[i-1][j-1] + C[i-1][j]。n 小用递推（无除法，取模简单）。练习杨辉三角递推法算组合数。

提示：每行首尾是1，中间用上一行两个数相加。C[i][0]=C[i][i]=1，C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD。

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, MOD = 1e9 + 7;
long long C[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        C[i][0] = 1;                          // 每行首是1
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;   // 递推
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++)
            cout << C[i][j] << " \n"[j == i];
    }
    return 0;
}

第 3 题：选队长（排列组合综合 —— 练区分）

题意：从 n 个人中选出 m 个人组成一个小组，并从这 m 个人中指定 1 个当队长。求方案数，对 10⁹+7 取模。

输入样例
5 3

输出样例
30

（先选3人 C(5,3)=10 种，再从3人中选1个当队长有3种，10×3=30）

考点：组合 + 乘法原理。方案数 = C(n,m) × m（选m个人 × 从m人中选队长）。练习"分步计数用乘法原理"——先组合选人，再选队长。

提示：① C(n,m) 选出小组（不讲顺序，用组合）；② 乘以 m（从 m 人中选队长，m 种选择）；③ 取模。也可以理解为 C(n,m)×C(m,1)。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N], inv_fact[N];

long long qpow(long long a, long long b, long long p) {
    long long res = 1; a %= p;
    while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }
    return res;
}
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD-2, MOD);
    for (int i = n-1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}

int main() {
    init(1000000);
    int n, m;
    cin >> n >> m;
    cout << C(n, m) * m % MOD << "\n";    // 选m人 × 选队长m种
    return 0;
}

第 4 题：分糖果（隔板法 —— 经典模型）

题意：把 n 个相同的糖果分给 k 个小朋友，每个小朋友至少分到 1 个。求有多少种不同的分法，对 10⁹+7 取模。

输入样例
5 3

输出样例
6

（5个糖果分给3人每人至少1个：(1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1)，共6种 = C(4,2)=6）

考点：隔板法。把 n 个相同物品分给 k 人每人至少1个 = C(n-1, k-1)（在 n 个物品的 n-1 个空隙插 k-1 个隔板）。练习识别和套用隔板法。

提示：① 隔板法公式 C(n-1, k-1)；② 用组合数取模计算；③ 理解：n个糖果排成一排有n-1个空隙，插k-1个板分成k段，每段至少1个。例：5个糖果分3人 = C(4,2)=6。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N], inv_fact[N];

long long qpow(long long a, long long b, long long p) {
    long long res = 1; a %= p;
    while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }
    return res;
}
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD-2, MOD);
    for (int i = n-1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}

int main() {
    init(1000000);
    int n, k;
    cin >> n >> k;
    cout << C(n - 1, k - 1) << "\n";      // 隔板法
    return 0;
}

第 5 题：网格路径计数（路径计数 —— 组合数解法）

题意：在 m × n 的网格中，从左上角 (0,0) 走到右下角 (m-1, n-1)，每次只能向右或向下走一步。求有多少条不同的路径，对 10⁹+7 取模。（这次用组合数公式，不用DP）

输入样例
3 4

输出样例
10

（3行4列，需要向下2步、向右3步，共5步选2步向下 = C(5,2)=10）

考点：路径计数 = 组合数。从左上到右下要走 (m-1) 步向下 + (n-1) 步向右，共 (m-1)+(n-1) 步，从中选 (m-1) 步向下 = C(m+n-2, m-1)。练习"路径计数用组合数"——对比3.1的DP解法，组合数更直接。

提示：① 总步数 = (m-1)+(n-1) = m+n-2；② 从总步数中选 m-1 步向下（或 n-1 步向右）；③ 答案 = C(m+n-2, m-1)。这和3.1不同路径题是同一问题的两种解法（DP vs 组合数）。

参考答案，写完再看：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, MOD = 1e9 + 7;
long long fact[N], inv_fact[N];

long long qpow(long long a, long long b, long long p) {
    long long res = 1; a %= p;
    while (b) { if (b&1) res=res*a%p; a=a*a%p; b>>=1; }
    return res;
}
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = qpow(fact[n], MOD-2, MOD);
    for (int i = n-1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}

int main() {
    init(1000000);
    int m, n;
    cin >> m >> n;
    // 走 (m-1)步下 + (n-1)步右，从总步数选 m-1 步向下
    cout << C(m + n - 2, m - 1) << "\n";
    return 0;
}

考点回顾：

1. 组合数取模 —— 阶乘+逆元（必会模板）
2. 杨辉三角 —— 递推（小范围）
3. 选队长 —— 组合+乘法原理
4. 分糖果 —— 隔板法
5. 路径计数 —— 组合数解法

最该吃透的认知：

• 组合数取模模板（第1题）——阶乘+逆元 + 逆元递推优化，是n大时算组合数取模的标准方法，必须掌握。这是组合数学题的核心工具。
• 两种计算方法的选择——n小用杨辉三角递推（第2题，无除法）、n大用阶乘逆元（第1题）。
• 乘法原理与分步计数（第3题）——复杂计数拆成几步，每步方案数相乘。"先选人再分工" = C(n,m)×m。
• 隔板法（第4题）——"相同物品分组每份至少1个" = C(n-1,k-1)，经典模型要会识别。
• 路径计数（第5题）——网格路径 = 组合数 C(m+n-2,m-1)，和DP是同一问题的两种解法。识别"只走右/下的路径计数"可以直接用组合数。

核心记忆——组合数学要点：

排列A(n,m)=n!/(n-m)!  讲顺序
组合C(n,m)=n!/(m!(n-m)!)  不讲顺序
取模：n小杨辉三角递推，n大阶乘+逆元
隔板法：n个分k份每份≥1 = C(n-1,k-1)
路径：右下走 = C(总步数, 向下步数)

把组合数取模模板练熟 + 会判断排列/组合 + 认识隔板法和路径计数，组合数学就够铜牌用了。

🎉 到这里，第五部分数学 + 铜牌核心知识体系全部完成！

你已经走完了从第〇部分到第五部分的完整路线——实战技巧、基础算法、搜索、动态规划、图论、数学，这正是冲击区域赛铜牌所需的全部核心知识。从零基础一路走来，你现在手里有了一套完整的"武器库"。

接下来是把知识转化为实战能力的阶段。几个建议方向：

1. 认真做那套模拟赛 #1（强烈推荐）——检验综合运用能力，体验真实比赛节奏。
2. 大量刷题——按专题在 Codeforces（Div3/Div4）、AtCoder（ABC）、洛谷上练，把"知道"变成"会用"。
3. 定期打模拟赛 / VP——周末固定打一场，赛后补题。
4. 回头补薄弱点——哪个模块做题总卡，针对性强化。
5. 选学剩余章节——字符串（哈希/KMP）、树状数组等，是锦上添花。