分享丨【算法题单】数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。原文链接：https://leetcode.cn/circle/discuss/IYT3ss/

$数学题单数学题目力扣数学题单 leetcode数学数论组合博弈几何随机灵茶山艾府灵神灵神题单$

图：暴力？NO！数学做法，降维打击！

前言

本文全面整理了力扣上的数学相关题目，其中数论和组合数学的题目比较多。

部分题目（尤其是组合数学）会涉及到取模，我写了一篇详细的取模教程，请看模运算的世界：当加减乘除遇上取模。

一、数论

§1.1 判断质数

如何判断一个正整数 $n$ 是不是质数？

只需判断 $n$ 能否能被 $\sqrt{n}$ 以内的某个大于 $1$ 的整数整除，如果不能则说明 $n$ 是质数。为什么？

反证法：如果 $n$ 不能被 $\sqrt{n}$ 以内的大于 $1$ 的整数整除，但可以被大于 $\sqrt{n}$ 的整数 $d (d < n)$ 整除，那么必然还有一个数 $\frac{n}{d}$ 也能整除 $n$ 。但是 $\frac{n}{d} < \frac{n}{\sqrt{n}} = \sqrt{n}$ ，说明存在一个 $\sqrt{n}$ 以内的大于 $1$ 的整数能整除 $n$ ，矛盾。

注意 $1$ 不是质数。

模板：

# 时间复杂度 O(sqrt(n))
def is_prime(n: int) -> bool:
    for i in range(2, isqrt(n) + 1):
        if n % i == 0:
            return False
    return n >= 2  # 1 不是质数

java

class Solution {
    // 时间复杂度 O(sqrt(n))
    private boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return n >= 2; // 1 不是质数
    }
}

cpp

// 时间复杂度 O(sqrt(n))
bool is_prime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2; // 1 不是质数
}

// 时间复杂度 O(sqrt(n))
func isPrime(n int) bool {
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            return false
        }
    }
    return n >= 2 // 1 不是质数
}

更快的模板（写法二）

§1.2 预处理质数（筛质数）

模板（埃氏筛）：

# 时间复杂度 O(MX * log log MX)
MX = 1_000_001
is_prime = [False] * 2 + [True] * (MX - 2)  # 0 和 1 不是质数
primes = []
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False  # j 是质数 i 的倍数

java

// 时间复杂度 O(MX * log log MX)
class Solution {
    private static final int MX = 1_000_001;
    private static final boolean[] isPrime = new boolean[MX];
    private static final List<Integer> primes = new ArrayList<>();
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数
        for (int i = 2; i < MX; i++) {
            if (isPrime[i]) {
                primes.add(i);
                for (long j = (long) i * i; j < MX; j += i) {
                    isPrime[(int) j] = false; // j 是质数 i 的倍数
                }
            }
        }
    }

    public int solve(int[] nums) {
        
    }
}

cpp

// 时间复杂度 O(MX * log log MX)
constexpr int MX = 1'000'001;
bool is_prime[MX];
vector<int> primes;

auto init = [] {
    ranges::fill(is_prime, true);
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是质数
    for (int i = 2; i < MX; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (long long j = 1LL * i * i; j < MX; j += i) {
                is_prime[j] = false; // j 是质数 i 的倍数
            }
        }
    }
    return 0;
}();

// 时间复杂度 O(mx * log log mx)
const mx = 1_000_001

var np = [mx]bool{true, true} // 0 和 1 不是质数
var primes []int

func init() {
    for i := 2; i < mx; i++ {
        if !np[i] {
            primes = append(primes, i)
            for j := i * i; j < mx; j += i {
                np[j] = true
            }
        }
    }
}

§1.3 质因数分解

模板一：预处理每个数的所有不同质因子。原理同埃氏筛。

MX = 1_000_001
prime_factors = [[] for _ in range(MX)]
for i in range(2, MX):
    if not prime_factors[i]:  # i 是质数
        for j in range(i, MX, i):  # i 的倍数 j 有质因子 i
            prime_factors[j].append(i)

java

class Solution {
    private static final int MX = 1_000_001;
    private static final List<Integer>[] primeFactors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(primeFactors, _ -> new ArrayList<>());
        for (int i = 2; i < MX; i++) {
            if (primeFactors[i].isEmpty()) { // i 是质数
                for (int j = i; j < MX; j += i) { // i 的倍数 j 有质因子 i
                    primeFactors[j].add(i);
                }
            }
        }
    }

    public int solve(int[] nums) {
        
    }
}

cpp

constexpr int MX = 1'000'001;
vector<int> prime_factors[MX];

int init = [] {
    for (int i = 2; i < MX; i++) {
        if (prime_factors[i].empty()) { // i 是质数
            for (int j = i; j < MX; j += i) { // i 的倍数 j 有质因子 i
                prime_factors[j].push_back(i);
            }
        }
    }
    return 0;
}();

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init() {
	for i := 2; i < mx; i++ {
		if primeFactors[i] == nil { // i 是质数
			for j := i; j < mx; j += i { // i 的倍数 j 有质因子 i
				primeFactors[j] = append(primeFactors[j], i)
			}
		}
	}
}

模板二：预处理 $x$ 的最小质因子 $LPF (x)$ ，从而做到 $O (\log x)$ 分解 $x$ ，求出 $x$ 的质因子及其出现次数。

MX = 1_000_001
lpf = [0] * MX
for i in range(2, MX):
    if lpf[i] == 0:  # i 是质数
        for j in range(i, MX, i):
            if lpf[j] == 0:  # 首次访问 j
                lpf[j] = i

# 质因数分解
# 例如 prime_factorization(45) = [(3, 2), (5, 1)]，表示 45 = 3**2 * 5**1
# 时间复杂度 O(log x)
def prime_factorization(x: int) -> List[Tuple[int, int]]:
    res = []
    while x > 1:
        p = lpf[x]
        e = 1
        x //= p
        while x % p == 0:
            e += 1
            x //= p
        res.append((p, e))
    return res

java

class Solution {
    private static final int MX = 1_000_001;
    private static final int[] lpf = new int[MX];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        for (int i = 2; i < MX; i++) {
            if (lpf[i] == 0) { // i 是质数
                for (int j = i; j < MX; j += i) {
                    if (lpf[j] == 0) { // 首次访问 j
                        lpf[j] = i;
                    }
                }
            }
        }
    }

    // 质因数分解
    // 例如 primeFactorization(45) = [[3, 2], [5, 1]]，表示 45 = 3^2 * 5^1
    // 时间复杂度 O(log x)
    private List<int[]> primeFactorization(int x) {
        List<int[]> res = new ArrayList<>();
        while (x > 1) {
            int p = lpf[x];
            int e = 1;
            for (x /= p; x % p == 0; x /= p) {
                e++;
            }
            res.add(new int[]{p, e});
        }
        return res;
    }

    public int solve(int[] nums) {
        
    }
}

cpp

constexpr int MX = 1'000'001;
int lpf[MX];

int init = [] {
    for (int i = 2; i < MX; i++) {
        if (lpf[i] == 0) { // i 是质数
            for (int j = i; j < MX; j += i) {
                if (lpf[j] == 0) { // 首次访问 j
                    lpf[j] = i;
                }
            }
        }
    }
    return 0;
}();

// 质因数分解
// 例如 prime_factorization(45) = {{3, 2}, {5, 1}}，表示 45 = 3^2 * 5^1
// 时间复杂度 O(log x)
vector<pair<int, int>> prime_factorization(int x) {
    vector<pair<int, int>> res;
    while (x > 1) {
        int p = lpf[x];
        int e = 1;
        for (x /= p; x % p == 0; x /= p) {
            e++;
        }
        res.emplace_back(p, e);
    }
    return res;
}

const mx = 1_000_001

var lpf = [mx]int{}

func init() {
	for i := 2; i < mx; i++ {
		if lpf[i] == 0 { // i 是质数
			for j := i; j < mx; j += i {
				if lpf[j] == 0 { // 首次访问 j
					lpf[j] = i
				}
			}
		}
	}
}

// 质因数分解
// 例如 primeFactorization(45) = [[3, 2], [5, 1]]，表示 45 = 3^2 * 5^1
// 时间复杂度 O(log x)
func primeFactorization(x int) (res [][2]int) {
	for x > 1 {
		p := lpf[x]
		e := 1
		for x /= p; x%p == 0; x /= p {
			e++
		}
		res = append(res, [2]int{p, e})
	}
	return
}

§1.4 阶乘分解

§1.5 因子

注：预处理质因子的模板在「§1.3 质因数分解」中。

模板（预处理每个数的所有因子）：

# 预处理每个数的因子
MX = 1_000_001  # **根据题目调整**
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
    for j in range(i, MX, i):  # 枚举 i 的倍数 j
        divisors[j].append(i)  # i 是 j 的因子

java

class Solution {
    private static final int MX = 1_000_001; // **根据题目调整**
    private static final List<Integer>[] divisors = new ArrayList[MX];
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        Arrays.setAll(divisors, _ -> new ArrayList<>());
        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
                divisors[j].add(i); // i 是 j 的因子
            }
        }
    }

    public int solve(int[] nums) {
        
    }
}

cpp

constexpr int MX = 1'000'001; // **根据题目调整**
vector<int> divisors[MX];

int init = [] {
    for (int i = 1; i < MX; i++) {
        for (int j = i; j < MX; j += i) { // 枚举 i 的倍数 j
            divisors[j].push_back(i); // i 是 j 的因子
        }
    }
    return 0;
}();

const mx = 1_000_001 // **根据题目调整**

var divisors [mx][]int // 如果 mx 很大可能会 MLE，可以改成 int32

func init() {
	for i := 1; i < mx; i++ {
		for j := i; j < mx; j += i { // 枚举 i 的倍数 j
			divisors[j] = append(divisors[j], i) // i 是 j 的因子
		}
	}
}

§1.6 最大公约数（GCD）

部分语言的标准库没有 GCD 和 LCM，需要手写。推荐写迭代，比递归快一点。

java

class Solution {
    private long gcd(long a, long b) {
        while (a != 0) {
            long tmp = a;
            a = b % a;
            b = tmp;
        }
        return b;
    }

    // 推荐先除后乘，尽量避免溢出
    private long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }
}

func gcd(a, b int) int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

// 推荐先除后乘，尽量避免溢出
func lcm(a, b int) int {
    return a / gcd(a, b) * b
}

1979. 找出数组的最大公约数 1184
3658. 奇数和与偶数和的最大公约数 1220
2169. 得到 0 的操作数非暴力做法
914. 卡牌分组 1371
1071. 字符串的最大公因子 1398
2344. 使数组可以被整除的最少删除次数 1641
365. 水壶问题
2654. 使数组所有元素变成 1 的最少操作次数 1929
1250. 检查「好数组」 1983 裴蜀定理
1625. 执行操作后字典序最小的字符串 1992 裴蜀定理
2607. 使子数组元素和相等 2071 裴蜀定理
2447. 最大公因数等于 K 的子数组数目
2543. 判断一个点是否可以到达 2221
3574. 最大子数组 GCD 分数 2300
3312. 查询排序后的最大公约数 2533 倍数容斥附变形题：1) 子序列 GCD 2) 树上路径 GCD
3725. 统计每一行选择互质整数的方案数倍数容斥
1819. 序列中不同最大公约数的数目 2540 调和级数枚举
3901. 好子序列查询 2545 证明
3671. 子序列美丽值求和 2647 倍数容斥
2436. 使子数组最大公约数大于一的最小分割数（会员题）
2464. 有效分割中的最少子数组数目（会员题）
2941. 子数组的最大 GCD-Sum（会员题）

扩展：

2807. 在链表中插入最大公约数 1279

§1.7 最小公倍数（LCM）

2413. 最小偶倍数 1145
3334. 数组的最大因子得分 1519
858. 镜面反射 1881
2197. 替换数组中的非互质数 2057
2470. 最小公倍数为 K 的子数组数目 logTrick 做到 $O (n \log k)$

§1.8 互质

§1.9 同余

§1.10 数论分块

1925. 统计平方和三元组的数目本原勾股数组

§1.11 莫比乌斯函数

数论中的容斥原理。

3953. 互质元素的最大得分 2390
3336. 最大公约数相等的子序列数量更快的做法

§1.12 其他

1018. 可被 5 整除的二进制前缀 1376
326. 3 的幂做到 $O (1)$
1387. 将整数按权重排序 1507 考拉兹猜想冰雹猜想
372. 超级次方欧拉定理
1015. 可被 K 整除的最小整数欧拉定理、欧拉函数
3790. 最小全 1 倍数同 1015 题
633. 平方数之和费马平方和定理
279. 完全平方数四平方和定理
2240. 买钢笔和铅笔的方案数类欧几里得算法

二、组合数学

§2.1 乘法原理

§2.2 组合计数

预处理阶乘及其逆元后，可以 $O (1)$ 计算组合数，模板代码如下。原理见模运算的世界：当加减乘除遇上取模。

MOD = 1_000_000_007
MX = 100_001  # 根据题目数据范围修改

fac = [0] * MX  # fac[i] = i!
fac[0] = 1
for i in range(1, MX):
    fac[i] = fac[i - 1] * i % MOD

inv_f = [0] * MX  # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
    inv_f[i - 1] = inv_f[i] * i % MOD

# 从 n 个数中选 m 个数的方案数
def comb(n: int, m: int) -> int:
    return fac[n] * inv_f[m] * inv_f[n - m] % MOD if 0 <= m <= n else 0

class Solution:
    def solve(self, nums: List[int]) -> int:
        # 把预处理的逻辑写在 class 外面，这样只会初始化一次

java

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 100_001; // 根据题目数据范围修改

    private static final long[] F = new long[MX]; // F[i] = i!
    private static final long[] INV_F = new long[MX]; // INV_F[i] = i!^-1 = pow(i!, MOD-2)

    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        F[0] = 1;
        for (int i = 1; i < MX; i++) {
            F[i] = F[i - 1] * i % MOD;
        }

        INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            INV_F[i - 1] = INV_F[i] * i % MOD;
        }
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }

    // 从 n 个数中选 m 个数的方案数
    private long comb(int n, int m) {
        return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
    }

    public int solve(int[] nums) {
        
    }
}

cpp

const int MOD = 1'000'000'007;
const int MX = 100'001; // 根据题目数据范围修改

long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1 = qpow(i!, MOD-2)

long long qpow(long long x, int n) {
    long long res = 1;
    for (; n; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) {
        F[i] = F[i - 1] * i % MOD;
    }

    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }
    return 0;
}();

// 从 n 个数中选 m 个数的方案数
long long comb(int n, int m) {
    return m < 0 || m > n ? 0 : F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}

class Solution {
public:
    int solve(vector<int>& nums) {
        // 把预处理的逻辑写在 class 外面，这样只会初始化一次
    }
};

const mod = 1_000_000_007
const mx = 100_001 // 根据题目数据范围修改

var fac [mx]int  // fac[i] = i!
var invF [mx]int // invF[i] = i!^-1 = pow(i!, mod-2)

func init() {
    fac[0] = 1
    for i := 1; i < mx; i++ {
        fac[i] = fac[i-1] * i % mod
    }

    invF[mx-1] = pow(fac[mx-1], mod-2)
    for i := mx - 1; i > 0; i-- {
        invF[i-1] = invF[i] * i % mod
    }
}

func pow(x, n int) int {
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

// 从 n 个数中选 m 个数的方案数
func comb(n, m int) int {
    if m < 0 || m > n {
        return 0
    }
    return fac[n] * invF[m] % mod * invF[n-m] % mod
}

func solve(nums []int) int {
    // 预处理的逻辑写在 init 函数中，这样只会初始化一次
}

62. 不同路径
357. 统计各位数字都不同的数字个数
1175. 质数排列 1489
3179. K 秒后第 N 个元素的值组合公式
1359. 有效的快递序列数目 1723
2400. 恰好移动 k 步到达某一位置的方法数目 1751
3881. 恰好看到 K 个人的方向选择 1761
3558. 给边赋权值的方案数 I 1845
3821. 二进制中恰好K个1的第N小整数 2069
762. 二进制表示中质数个计算置位非暴力做法
2514. 统计同位异构字符串数目 2070
3154. 到达第 K 级台阶的方案数 2071
1643. 第 K 条最小指令 2080
2842. 统计一个字符串的 k 子序列美丽值最大的数目 2092
2221. 数组的三角和扩展卢卡斯组合数模 $10$
3463. 判断操作后字符串中的数字是否相等 II 2286 扩展卢卡斯组合数模 $10$
3519. 统计逐位非递减的整数 2246
3906. 统计网格路径中好整数的数目类似 3519 题
1569. 将子数组重新排序得到同一个二叉搜索树的方案数 2288
3405. 统计恰好有 K 个相等相邻元素的数组数目 2310
1866. 恰有 K 根木棍可以看到的排列数目 2333 第一类斯特林数
1467. 两个盒子中球的颜色数相同的概率 2357
3518. 最小回文排列 II 2375 试填法多重集排列数
3272. 统计好整数的数目 2382
3317. 安排活动的方案数 2414 第二类斯特林数
3470. 全排列 IV 2474 构造，字典序第 $k$ 小
1916. 统计为蚁群构筑房间的不同顺序 2486 拓扑序方案数
3343. 统计平衡排列的数目 2615 多重集排列数
1830. 使字符串有序的最少操作次数 2620
2954. 统计感冒序列的数目 2645
3539. 魔法序列的数组乘积之和 2694 多重集排列数
3395. 唯一中间众数子序列 I 2800 做到 $O (n)$ 时间
1575. 统计所有可行路径
3251. 单调数组对的数目 II 做到 $O (n)$ 时间
LCP 25. 古董键盘
2539. 好子序列的个数（会员题）
634. 寻找数组的错位排列（会员题）
1692. 计算分配糖果的不同方式（会员题）第二类斯特林数

关于生成函数的题目，见本题单的「§2.5 生成函数」。

关于计数 DP 的题目，见动态规划题单的「§7.7 计数 DP」。

§2.3 放球问题

图解：多重集组合数

思维扩展：

3669. K 因数分解不是组合数学题，但分析算法的计算量需要用到组合数学

§2.4 容斥原理

部分题目有其他解法，难度分仅供参考。

§2.5 生成函数（母函数）

注：贡献法移至贪心与思维题单。

三、概率期望

随机数据下显著更快的算法：

3494. 酿造药水需要的最少总时间

四、博弈论

五、计算几何

§5.1 点、线

§5.2 圆

§5.3 矩形、多边形

§5.4 凸包

模板：

class Vec:
    __slots__ = 'x', 'y'

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __sub__(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x


# Andrew 算法，计算 points 的凸包（逆时针顺序）
# 时间复杂度 O(n log n)，其中 n = len(points)
def convexHull(points: List[Vec]) -> List[Vec]:
    if len(points) <= 1:
        return points

    points.sort(key=lambda p: (p.x, p.y))

    q = []

    # 计算下凸包（从左到右）
    for p in points:
        # 新来的点 p，能否让旧的点变成在凸包内的点？ ->  需要判断向量左右关系  ->  det
        while len(q) > 1 and (q[-1] - q[-2]).det(p - q[-1]) <= 0:
            q.pop()
        q.append(p)

    # 计算上凸包（从右到左）
    # 注意下凸包的最后一个点，已经是上凸包的（右边）第一个点了，所以从 n-2 开始遍历
    lower_size = len(q)
    for i in range(len(points) - 2, -1, -1):
        p = points[i]
        while len(q) > lower_size and (q[-1] - q[-2]).det(p - q[-1]) <= 0:
            q.pop()
        q.append(p)

    # 此时首尾是同一个点 points[0]，需要去掉
    q.pop()

    return q

java

class Vec {
    int x, y;

    Vec(int x, int y) {
        this.x = x;
        this.y = y;
    }

    Vec sub(Vec b) {
        return new Vec(x - b.x, y - b.y);
    }

    long det(Vec b) {
        return (long) x * b.y - (long) y * b.x;
    }
}

class Solution {
    // Andrew 算法，计算 points 的凸包（逆时针顺序）
    // 时间复杂度 O(n log n)，其中 n = points.size()
    public List<Vec> convexHull(List<Vec> points) {
        if (points.size() <= 1) {
            return points;
        }

        points.sort((a, b) -> a.x != b.x ? a.x - b.x : a.y - b.y);

        List<Vec> q = new ArrayList<>();

        // 计算下凸包（从左到右）
        for (Vec p : points) {
            // 新来的点 p，能否让旧的点变成在凸包内的点？ ->  需要判断向量左右关系  ->  det
            while (q.size() > 1 && q.getLast().sub(q.get(q.size() - 2)).det(p.sub(q.getLast())) <= 0) {
                q.removeLast();
            }
            q.add(p);
        }

        // 计算上凸包（从右到左）
        // 注意下凸包的最后一个点，已经是上凸包的（右边）第一个点了，所以从 n-2 开始遍历
        int lowerSize = q.size();
        for (int i = points.size() - 2; i >= 0; i--) {
            Vec p = points.get(i);
            while (q.size() > lowerSize && q.getLast().sub(q.get(q.size() - 2)).det(p.sub(q.getLast())) <= 0) {
                q.removeLast();
            }
            q.add(p);
        }

        // 此时首尾是同一个点 points[0]，需要去掉
        q.removeLast();

        return q;
    }
}

cpp

struct Vec {
    int x, y;

    Vec sub(const Vec& b) const {
        return {x - b.x, y - b.y};
    }

    long long det(const Vec& b) const {
        return 1LL * x * b.y - 1LL * y * b.x;
    }
};

// Andrew 算法，计算 points 的凸包（逆时针顺序）
// 时间复杂度 O(n log n)，其中 n = points.size()
vector<Vec> convexHull(vector<Vec>& points) {
    ranges::sort(points, {}, [](auto& p) { return pair(p.x, p.y); });

    vector<Vec> q;

    // 计算下凸包（从左到右）
    for (auto& p : points) {
        // 新来的点 p，能否让旧的点变成在凸包内的点？ ->  需要判断向量左右关系  ->  det
        while (q.size() > 1 && q.back().sub(q[q.size() - 2]).det(p.sub(q.back())) <= 0) {
            q.pop_back();
        }
        q.push_back(p);
    }

    // 计算上凸包（从右到左）
    // 注意下凸包的最后一个点，已经是上凸包的（右边）第一个点了，所以从 n-2 开始遍历
    int lower_size = q.size();
    for (int i = (int) points.size() - 2; i >= 0; i--) {
        auto& p = points[i];
        while (q.size() > lower_size && q.back().sub(q[q.size() - 2]).det(p.sub(q.back())) <= 0) {
            q.pop_back();
        }
        q.push_back(p);
    }

    // 此时首尾是同一个点 points[0]，需要去掉
    q.pop_back();

    return q;
}

type vec struct{ x, y int }

func (a vec) sub(b vec) vec { return vec{a.x - b.x, a.y - b.y} }
func (a vec) det(b vec) int { return a.x*b.y - a.y*b.x }

// Andrew 算法，计算 points 的凸包（逆时针顺序）
// 时间复杂度 O(n log n)，其中 n = len(points)
func convexHull(points []vec) []vec {
    if len(points) <= 1 {
        return points
    }

    slices.SortFunc(points, func(a, b vec) int { return cmp.Or(a.x-b.x, a.y-b.y) })

    q := []vec{}

    // 计算下凸包（从左到右）
    for _, p := range points {
        // 新来的点 p，能否让旧的点变成在凸包内的点？ ->  需要判断向量左右关系  ->  det
        for len(q) > 1 && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) <= 0 {
            q = q[:len(q)-1]
        }
        q = append(q, p)
    }

    // 计算上凸包（从右到左）
    // 注意下凸包的最后一个点，已经是上凸包的（右边）第一个点了，所以从 n-2 开始遍历
    lowerSize := len(q)
    for i := len(points) - 2; i >= 0; i-- {
        p := points[i]
        for len(q) > lowerSize && q[len(q)-1].sub(q[len(q)-2]).det(p.sub(q[len(q)-1])) <= 0 {
            q = q[:len(q)-1]
        }
        q = append(q, p)
    }

    // 此时首尾是同一个点 points[0]，需要去掉
    q = q[:len(q)-1]

    return q
}

另见动态规划题单的「§11.7 斜率优化 DP」。

§5.5 其他

3899. 三角形的内角度数 1407

六、随机算法

§6.1 随机数

§6.2 随机化技巧

七、杂项

§7.1 回文数

从小到大枚举回文数的模板（从 $1$ 开始枚举）：

def gen_palindrome() -> Iterator[int]:
    base = 1
    while True:
        # 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
        for i in range(base, base * 10):
            s = str(i)
            x = int(s + s[::-1][1:])
            yield x

        # 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
        for i in range(base, base * 10):
            s = str(i)
            x = int(s + s[::-1])
            yield x

        base *= 10


for x in gen_palindrome():
    if x > 10 ** 9:  # 根据题目调整
        break
    # 处理 x 的逻辑写下面
    print(x)

java

class Solution {
    private static final long MX = 10_000_000_000L; // 根据题目调整
    private static final List<Long> palindromes = new ArrayList<>();
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        for (int base = 1; ; base *= 10) {
            // 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
            for (int i = base; i < base * 10; i++) {
                long x = i;
                for (int t = i / 10; t > 0; t /= 10) {
                    x = x * 10 + t % 10;
                }
                if (x > MX) {
                    return;
                }
                palindromes.add(x);
            }

            // 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
            for (int i = base; i < base * 10; i++) {
                long x = i;
                for (int t = i; t > 0; t /= 10) {
                    x = x * 10 + t % 10;
                }
                if (x > MX) {
                    return;
                }
                palindromes.add(x);
            }
        }
    }

    public int solve(int n) {
        
    }
}

cpp

const long long MX = 10'000'000'000LL; // 根据题目调整
vector<long long> palindromes;

// 预处理 [1,MX] 中的回文数
auto init = []() {
    for (int base = 1; ; base *= 10) {
        // 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
        for (int i = base; i < base * 10; i++) {
            long long x = i;
            for (int t = i / 10; t > 0; t /= 10) {
                x = x * 10 + t % 10;
            }
            if (x > MX) {
                return 0;
            }
            palindromes.push_back(x);
        }

        // 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
        for (int i = base; i < base * 10; i++) {
            long long x = i;
            for (int t = i; t > 0; t /= 10) {
                x = x * 10 + t % 10;
            }
            if (x > MX) {
                return 0;
            }
            palindromes.push_back(x);
        }
    }
}();

const mx = 10_000_000_000 // 根据题目调整

var palindromes []int

// 预处理 [1,mx] 中的回文数
func init() {
    for base := 1; ; base *= 10 {
        // 生成奇数长度回文数，例如 base = 10，生成的范围是 101 ~ 999
        for i := base; i < base*10; i++ {
            x := i
            for t := i / 10; t > 0; t /= 10 {
                x = x*10 + t%10
            }
            if x > mx {
                return
            }
            palindromes = append(palindromes, x)
        }

        // 生成偶数长度回文数，例如 base = 10，生成的范围是 1001 ~ 9999
        for i := base; i < base*10; i++ {
            x := i
            for t := i; t > 0; t /= 10 {
                x = x*10 + t%10
            }
            if x > mx {
                return
            }
            palindromes = append(palindromes, x)
        }
    }
}

§7.2 整数拆分

§7.3 曼哈顿距离与切比雪夫距离

§7.4 多项式

611. 有效三角形的个数做到 $O (n + U \log U)$
923. 三数之和的多种可能做到 $O (n + U \log U)$
835. 图像重叠
3549. 两个多项式相乘（会员题）FFT 模板
259. 较小的三数之和（会员题）做到 $O (n + U \log U)$
3078. 矩阵中的字母数字模式匹配 I（会员题）
3400. 右移后的最大匹配索引数（会员题）根号分解

另见本题单的「§2.6 生成函数」。

§7.5 快速沃尔什变换（FWT）

§7.6 拉格朗日插值

3916. 锯齿形数组的总数 III（会员题）

§7.7 线性基

见位运算题单。

§7.8 摩尔投票法

§7.9 其他

1523. 在区间范围内统计奇数数目 1209
1716. 计算力扣银行的钱 1295
2829. k-avoiding 数组的最小总和 1347
2579. 统计染色格子数 1356
3648. 覆盖网格的最少传感器数目 1396
2834. 找出美丽数组的最小和 1409
1414. 和为 K 的最少斐波那契数字数目 1466
319. 灯泡开关约 1500
1780. 判断一个数字是否可以表示成三的幂的和 1506
3091. 执行操作使数据元素之和大于等于 K 1522
3468. 可行数组的数目 1545 数学推导
2310. 个位数字为 K 的整数之和 1559
2145. 统计隐藏数组数目 1614 数学推导
2541. 使数组中所有元素相等的最小操作数 II 1620
1502. 判断能否形成等差数列做到 $O (n)$
2195. 向数组中追加 K 个整数 1659
2457. 美丽整数的最小增量 1680
1017. 负二进制转换 1698
3649. 完美对的数目 1716 绝对值的几何意义
1954. 收集足够苹果的最小花园周长 1759
1073. 负二进制数相加 1807
1823. 找出游戏的获胜者约瑟夫环
166. 分数到小数有数学做法，可以不用哈希表
3012. 通过操作使数组长度最小 1833
483. 最小好进制
3782. 交替删除操作后最后剩下的整数 2074
390. 消除游戏类似 3782 题
1680. 连接连续二进制数字做到 $O (\log^{2} n)$
972. 相等的有理数 2121
1515. 服务中心的最佳位置 2157 凸优化梯度下降法
1862. 向下取整数对和 2170 调和级数枚举
1739. 放置盒子 2198
2443. 反转之后的数字和非暴力做法
1806. 还原排列的最少操作步数非暴力做法
458. 可怜的小猪
31. 下一个排列
60. 排列序列
2117. 一个区间内所有数乘积的缩写 2477
3666. 使二进制字符串全为 1 的最少操作次数 2477 Gale-Ryser 定理
LCP 02. 分式化简连分数
LCP 29. 乐团站位
LCP 46. 志愿者调配解方程
800. 相似 RGB 颜色（会员题）
660. 移除 9（会员题）
2979. 最贵的无法购买的商品（会员题）
2647. 把三角形染成红色（会员题）

算法题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

数据结构

数据库

离散数学

数字电路

概率论

数学建模

软件工程

面向对象程序设计

Python 与数据分析

计算机组成

操作系统

计算机网络

编译原理

图形学

自然语言处理

Linux 实验

分布式系统

Internet原理与技术

BlogWeb

Stars Saying

黑马商城

苍穹外卖

黑马点评

黑马商城单体版

JavaWeb AI Tlias

RuoYi DKD

LinkQwen

InterX

LeetCode Agent Lab

00-预备知识

01-PR1108-逐代码段解析

02-PR1135-Cube化逐代码段解析

03-两个Bug深度剖析

04-开发心得与数值性能实测

01-PR1169-模型推理性能优化

02-PR1194-固定Shape及分档推理适配

NumPy

PyTorch

Python 八股文

LeetCUDA

LeetGPU

Triton

前言 ​

一、数论 ​

§1.1 判断质数 ​

§1.2 预处理质数（筛质数） ​

§1.3 质因数分解 ​

§1.4 阶乘分解 ​

§1.5 因子 ​

§1.6 最大公约数（GCD） ​

§1.7 最小公倍数（LCM） ​

§1.8 互质 ​

§1.9 同余 ​

§1.10 数论分块 ​

§1.11 莫比乌斯函数 ​

§1.12 其他 ​

二、组合数学 ​

§2.1 乘法原理 ​

§2.2 组合计数 ​

§2.3 放球问题 ​

§2.4 容斥原理 ​

§2.5 生成函数（母函数） ​

三、概率期望 ​

四、博弈论 ​

五、计算几何 ​

§5.1 点、线 ​

§5.2 圆 ​

§5.3 矩形、多边形 ​

§5.4 凸包 ​

§5.5 其他 ​

六、随机算法 ​

§6.1 随机数 ​

§6.2 随机化技巧 ​

七、杂项 ​

§7.1 回文数 ​

§7.2 整数拆分 ​

§7.3 曼哈顿距离与切比雪夫距离 ​

§7.4 多项式 ​

§7.5 快速沃尔什变换（FWT） ​

§7.6 拉格朗日插值 ​

前言

一、数论

§1.1 判断质数

§1.2 预处理质数（筛质数）

§1.3 质因数分解

§1.4 阶乘分解

§1.5 因子

§1.6 最大公约数（GCD）

§1.7 最小公倍数（LCM）

§1.8 互质

§1.9 同余

§1.10 数论分块

§1.11 莫比乌斯函数

§1.12 其他

二、组合数学

§2.1 乘法原理

§2.2 组合计数

§2.3 放球问题

§2.4 容斥原理

§2.5 生成函数（母函数）

三、概率期望

四、博弈论

五、计算几何

§5.1 点、线

§5.2 圆

§5.3 矩形、多边形

§5.4 凸包

§5.5 其他

六、随机算法

§6.1 随机数

§6.2 随机化技巧

七、杂项

§7.1 回文数

§7.2 整数拆分

§7.3 曼哈顿距离与切比雪夫距离

§7.4 多项式

§7.5 快速沃尔什变换（FWT）

§7.6 拉格朗日插值

§7.7 线性基

§7.8 摩尔投票法

§7.9 其他

算法题单