数论与数学

数论与数学

数论与数学是竞赛的核心考查内容。共 14 个模板。

← 返回模板库

5.1素数判断

试除法判断单个数是否为素数

O(√n)

5.2埃氏筛

筛法求区间内所有素数

O(n log log n)

5.3欧拉筛（线性筛）

每个合数只被最小质因子筛一次

O(n)

5.4质因数分解

将合数分解为质因数的乘积

O(√n)

5.5GCD / LCM

辗转相除法求最大公约数和最小公倍数

O(log n)

5.6快速幂

二进制拆分指数，快速计算 a^b mod p

O(log b)

5.7扩展欧几里得

求解 ax + by = gcd(a, b) 的整数解

O(log n)

5.8组合数 - 杨辉三角

利用递推关系求组合数 C(n,m)

O(n²)

5.9组合数 - 逆元

用阶乘逆元 O(1) 查询组合数

O(n) 预处理, O(1) 查询

5.10欧拉函数

求 1~n 中与 n 互质的数的个数

O(√n)

5.11卡特兰数

经典计数问题，如括号匹配、出栈序列

O(n)

5.12矩阵快速幂

用矩阵加速线性递推

O(k³ log n)

5.13容斥原理

集合计数的加减交替公式

O(2^n)

5.14博弈论 - Nim 游戏

异或判断先手胜负

O(n)