最大公约数

__gcd(a, b)（C++17）或辗转相除法。

扩展欧几里得：求 $ax + by = \gcd(a,b)$ 的一组整数解。

素数

• 试除：$O(\sqrt{n})$ 判素、分解
• 埃氏筛：$O(n \log \log n)$ 筛 $1\sim n$
• 线性筛：每个合数只被最小质因子筛掉

快速幂

$$a^b \bmod p$$ 在 $O(\log b)$ 内完成，注意取模每一步。

long long powmod(long long a, long long b, long long mod) {
    long long r = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1) r = r * a % mod;
    return r;
}

组合数

预处理阶乘与逆元：

$$C_n^k = \frac{n!}{k!(n-k)!} \pmod p$$

$p$ 为质数时用逆元 inv[k] = powmod(fac[k], p-2, p)。

卢卡斯定理：大组合数模质数 $p$ 时，按 $n,k$ 的 $p$ 进制分解计算。

同余与逆元

• 费马小定理：$p$ 质数且 $p \nmid a$ 时 $a^{p-1} \equiv 1 \pmod p$，故 $a^{-1} \equiv a^{p-2}$
• 扩展欧几里得：求 $a^{-1} \bmod m$（$gcd(a,m)=1$）

欧拉函数

$\varphi(n)$：小于 $n$ 且与 $n$ 互质的个数。筛法预处理，分解质因数单次 $O(\sqrt n)$。

矩阵与线性递推

斐波那契第 $n$ 项：构造 $2\times 2$ 转移矩阵，快速幂 $O(\log n)$。

容斥原理

计数「至少满足一个条件」用全集减去不满足；多个条件用奇加偶减的 inclusion-exclusion。

例题

例 1：快速幂求余（洛谷 P1226）
求 $a^b \bmod p$（$p$ 可能为合数时注意是否只用欧拉定理；质数模用快速幂即可）。二进制拆 $b$，平方累乘，$O(\log b)$。

例 2：组合数取模（预处理阶乘）
从 $n$ 个点中选 $k$ 个的方案数 $C_n^k \bmod 10^9+7$。预处理 fac[i]、inv[i]，单次查询 fac[n]*inv[k]%p*inv[n-k]%p。$n$ 次询问总复杂度 $O(n + q)$。