1. 模运算

模运算（同余运算）是算法竞赛中最基础的数论工具。核心思想：先取模，再运算，最后再取模，结果不变。

$$ \begin{aligned} (a + b) \bmod m &= \big((a \bmod m) + (b \bmod m)\big) \bmod m \\[4pt] (a - b) \bmod m &= \big((a \bmod m) - (b \bmod m)\big) \bmod m \\[4pt] (a \times b) \bmod m &= \big((a \bmod m) \times (b \bmod m)\big) \bmod m \end{aligned} $$

⚠️ C++ 取模的坑

C++ 中 % 运算符遵循 「使商尽可能大」 的原则（向零取整），导致负数的模可能为负：

$$ -5 \bmod 3 = -2 \qquad\text{（C++ 中）} $$

🔧 安全减法取模公式：对减法取模时，多加一个 $m$ 再取模，避免负数：

$$ (a - b) \bmod m = \big((a \bmod m) - (b \bmod m) + m\big) \bmod m $$

2. 快速幂（二进制法）

快速幂利用 「二进制拆分指数」 的思想，将 $O(n)$ 的朴素幂运算优化到 $O(\log n)$。

核心：$a^n = a^{\,2^{k_1}} \cdot a^{\,2^{k_2}} \cdots$（按 $n$ 的二进制位拆分）

long long fastpow(long long x, long long n) {
    long long ans = 1;
    while (n) {
        if (n & 1)  ans = ans * x;   // 乘法过程中可同步取模
        x = x * x;
        n >>= 1;
    }
    return ans;
}

💡 实际应用中，只需在乘法处加上 % MOD 即可同时完成快速幂取模。

3. 最大公约数 & 最小公倍数

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

$$ \gcd(a, b) = \gcd(b, a \bmod b) $$

📖 证明思路：$d \mid a,\; d \mid b \;\Longleftrightarrow\; d \mid (a - b)$，反复相减即得。
推论：$\gcd(a, b) = \gcd(a - b, b)$，递归即得辗转相除。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

最小公倍数

$$ \operatorname{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} \qquad\text{常记为 } [a, b] $$

性质

• 可重复贡献：$\gcd(a, b, c) = \gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c))$
• 零元性质：$\gcd(a, 0) = a$
• 符号无关：$\gcd(a, b) = \gcd(a, -b)$
• $0$ 是 $\gcd$ 运算的基元（单位元）

4. 组合数

组合数，又称二项式系数，记作 $C(n, k)$ 或 $\binom{n}{k}$，表示从 $n$ 个不同元素中取出 $k$ 个元素（不考虑顺序）的不同方案数。

$$ C(n, k) = \binom{n}{k} = \frac{n!}{k!\,(n - k)!} $$

杨辉三角递推

利用组合数的递推性质，可以在 $O(n^2)$ 内预处理出所有组合数：

$$ C(n, k) = C(n-1, k-1) + C(n-1, k) $$

💡 直观理解：选第 $n$ 个元素 → 从前 $n-1$ 个中选 $k-1$ 个；不选第 $n$ 个元素 → 从前 $n-1$ 个中选 $k$ 个。

const int N = 2005;
int C[N][N];

void init_C() {
    C[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        C[i][0] = 1;                     // C(n, 0) = 1
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

5. 求质数（素数筛法）

• ✅ 试除法
• ✅ 埃拉托斯特尼筛法（埃氏筛）
• ⬜ 线性筛（欧拉筛）

埃氏筛

核心思想：素数的整数倍一定是合数。从小到大枚举，遇到素数就把它的所有倍数标记为合数。

vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;

for (int p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
        for (int i = p * p; i <= n; i += p) {
            isPrime[i] = false;
        }
    }
}

💡 优化细节：内层循环从 $p^2$ 开始（而非 $2p$），因为 $2p, 3p, \dots, (p-1)p$ 已被更小的素数筛过。

时间复杂度：$O(n \log\log n)$，接近线性。

6. 求解因数个数

与埃氏筛思想类似——「倍数即因数」：枚举每个数 $i$，给 $i$ 的所有倍数 $j$ 的因数计数 $+1$。

int n;
cin >> n;
vector<int> cnt(n + 1, 0);

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
        cnt[j]++;          // i 是 j 的一个因数
    }
}

📊 复杂度分析：调和级数 $\displaystyle\sum_{i=1}^{n}\frac{n}{i} = O(n \log n)$，对于 $n \le 10^6$ 完全可行。