数论内容知识点比较零碎且容易遗忘，因此便对其进行总结。
内容都为数论基础知识点，板子主要用
C++表示。
快速幂 #
标准的 a ^ b mod p 形式的快速幂：
long long fast_pow(long long i, long long n, long long mod) {
long long res = 1;
i = i % mod;
while (n) {
if (n & 1)
res = (res * i) % mod;
i = (i * i) % mod;
n >>= 1;
}
return res;
}
时间复杂度为:
$$ O(\log b) $$
如果要考虑非正数整数则：
double newX = 0;
if (b == 0)
return 1;
if (b < 0) {
b = -b;
newX = 1 / x;
}
C++ 的 pow() 库函数处理的是浮点数，因此在运行数值较大是会出现精度错误。在比赛或面试中，遇到指数大于十的幂运算时，就建议手搓快速幂。
python 的 pow() 不会有这个问题，可以放心使用。
标准的 a ^ b 形式的快速幂：
long long fast_pow(long long a, long long b) {
long long res = 1;
long long base = a;
while (b) {
if (b & 1)
res = (res * base);
base = (base * base);
b >>= 1;
}
return res;
}
最大公约数 #
一般而言，用库函数就可以了。
注意 gcd() 在 c++17 才引用，C++11 用 __gcd()。
辗转相除法的思想要了解下。
long long my_gcd(long long a, long long b) {
return __gcd(a, b); //
// 辗转相除法
// return b == 0 ? a : gcd(b, a % b);
}
裴蜀定理 #
设 a 和 b 是两个不全为零的整数。
对于任意整数 x 和 y ，都有：
$$ \gcd(a, b) \mid ax + by $$
也就是说，最大公约数 gcd(a, b) 总是整除形如 ax + by 的表达式。
不仅如此，还存在某些整数 x 和 y ，使得：
$$ ax + by = \gcd(a, b) $$
最小公倍数 #
最小公倍数为 abs(a * b) / __gcd(a, b)
long long lcm(long long a, long long b) {
return abs(a * b) / __gcd(a, b);
}
素数筛 #
素数筛目的是找出 2 到 n 的所有素数（即质数）。
埃式筛 #
埃式筛的基本思想从 2 到 N 枚举，如果当前数未被标记为合数，则其为素数，并将它的倍数全部标记为合数。
vector<bool> sieve_of_eratosthenes(int n) {
vector<bool>is_prime(n + 1, true);
// 0 和 1 不是素数
is_prime[0] = false;
is_prime[1] = false;
for(int i = 2; i * i <= n; i++)
if (is_prime[i])
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
return is_prime;
}
时间复杂度：
$$O\left(n \log \log n\right)$$
线性筛 #
相比埃式筛多维护一个已确定的质数数组。
vector<bool> sieve_of_eratosthenes(int n) {
vector<bool> is_prime(n + 1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
primes.push_back(i);
}
for (int p : primes) {
if (i * p > n) break; // 超出范围
is_prime[i * p] = false; // 标记 i * p 为非素数
if (i % p == 0) break; // 保证每个数只被其最小质因数筛选一次
}
}
return is_prime; // 返回布尔数组
}
时间复杂度：
$$O(n)$$
质因数分解 #
获取小于 n 的质因数集合。
- 质因数：能整除 n 的质数。
基本思想如下：
- n 的质因数最大不会超过 sqrt(n)。
- 从小到大找 n 的因数，每找到一个就将 n 反复除去该因数。
vector<long long> primeDivide(long long n) {
vector<long long>ans;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans.push_back(i);
// 如果要统计每个质因数的个数要在此处计数
while (n % i == 0) {
n /= i;
}
}
}
// n 本身是质数 要特判
if (n > 1) {
ans.push_back(n);
}
return ans;
}
时间复杂度：
$$O(\sqrt{n})$$
例题：
蓝桥杯 完全平方数 - 完全平方数的每个质因数的指数都是偶数
CSP认证 因子化简 - 质因数板子加简单判断
欧拉函数 #
求不超过 n 并且和 n 互为质数的个数。
- 互质：n 不为 m 的因数，m 也不为 n 的因数。
上面的质因数分解得到了 n 因数中的质数。
根据下面的欧拉函数：
$$\phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right)$$
$$\phi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_k} \right)$$
long long euler(long long n, long long MOD) {
// 1 的欧拉函数是 0
if (n == 1)
return 0;
vector<long long>factor;
factor = primeDivide(n);
// 如果 n 本身是质数，注意不能用 size 为 1 判断
if (factor[0] == n) {
return (n - 1) % MOD;
}
long long ans = n;
for (auto &i : factor) {
// 欧拉函数的公式
ans = ans * (i - 1) / i % MOD; // 注意要这样写才能不触发向下取整
}
return ans;
}
时间复杂度：
$$O(\sqrt{n})$$
例题：
蓝桥杯 互质数的个数 - 欧拉函数板子
逆元法求组合数 #
费马小定理：
若 p 是素数，且 a 是整数，满足 \( p \nmid a \) 即 a 不能被 p 整除，则有：
$$ a^{p-1} \equiv 1 \pmod{p} \ $$
组合数公式：
$$ \text{comb}(n, m) \equiv \frac{n!}{m!(n - m)!} \pmod{\text{MOD}} $$
$$ \text{comb}(n, m) \equiv \text{fact}[n] \cdot \text{inv}[m] \cdot \text{inv}[n - m] \pmod{\text{MOD}} $$
$$ 其中 \ \text{inv}[i] = \left( \text{fact}[i] \right)^{-1} \bmod \text{MOD} $$
根据费马小定理：
$$ inv[i] = fact[i]^{-1} \equiv fact[i]^{\text{MOD} - 2} \pmod{\text{MOD}} $$
此外有逆元递推式：
$$\text{inv}[i] = \text{inv}[i + 1] \times (i + 1) \bmod \text{MOD} \quad $$
const int MOD = 998244353; // 需要保证 MOD 是质数
const int MAXN = 2 * 100000 + 10;
vector<long long> inv(MAXN, 1);
vector<long long> fact(MAXN, 1);
// 快速幂
long long qpow(long long i, long long n, long long p) {
i %= p;
long long res = 1;
while (n) {
if (n & 1) {
res = (res * i) % p;
}
i = (i * i) % p;
n >>= 1;
}
return res;
}
// On 求阶乘数组
for (int i = 1; i < MAXN; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
// On 求逆元数组，inv[MAXN - 1] 用费马小定理
inv[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2, MOD);
for (int i = MAXN - 2; i >= 0; i--) { // 递推求逆元
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
// 也可以直接快速幂求
// inv[i] = qpow(fact[i], MOD - 2, MOD)
// 组合数公式，分母两个阶乘变成逆元
long long comb(int m, int n) {
return fact[m] * (inv[n] % MOD) % MOD * (inv[m - n] % MOD) % MOD;
}
python 的 pow 自带快速幂和逆元，能大大减小代码量（但 comb 对大数支持并不好）
MOD = 998244353
MAXN = 2 * 10**5 + 10
fact = [1] * MAXN
inv = [1] * MAXN
for i in range(1, MAXN):
fact[i] = fact[i - 1] * i % MOD
inv[MAXN - 1] = pow(fact[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
inv[i] = inv[i + 1] * (i + 1) % MOD
# 组合数 C(n, k)
def comb(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv[k] % MOD * inv[n - k] % MOD