图：暴力？NO！数学做法，降维打击！
前言
本文整理了力扣上的数学相关题目，主要以数论和组合数学为主。
部分题目（尤其是组合数学）会涉及到取模，我写了一篇教程，请看 模运算的世界：当加减乘除遇上取模。
一、数论
§1.1 判断质数
- 3115. 质数的最大距离 1294
- 2614. 对角线上的质数 1375
- 762. 二进制表示中质数个计算置位 1383
- 3556. 最大质数子字符串之和 1440
- 3044. 出现频率最高的质数 1737
- 866. 回文质数 1938
§1.2 预处理质数（筛质数）
- 204. 计数质数
- 2761. 和等于目标值的质数对 1505
- 3233. 统计不是特殊数字的数字数量 1509
- 2523. 范围内最接近的两个质数 1650
- 2601. 质数减法运算 1779
§1.3 质因数分解
可以预处理 x 的最小质因子 LPF(x)，从而做到 O(logx) 分解 x。
- 2521. 数组乘积中的不同质因数数目 1413
- 2507. 使用质因数之和替换后可以取到的最小值 1500
- 3326. 使数组非递减的最少除法操作次数 1864
- 2584. 分割数组使乘积互质 2159
- 2709. 最大公约数遍历 2172
- 2862. 完全子集的最大元素和 2292
- 2818. 操作使得分最大 2397
- 1998. 数组的最大公因数排序 2429
- 1735. 生成乘积数组的方案数 2500
- 2338. 统计理想数组的数目 2615
§1.4 阶乘分解
§1.5 因子
- 2427. 公因子的数目 1172
- 1952. 三除数 1204
- 1492. n 的第 k 个因子 1232
- 507. 完美数
- 1390. 四因数 1478
- 1362. 最接近的因数 1534
- 829. 连续整数求和 1694
- 3447. 将元素分配给有约束条件的组 1731 调和级数枚举
- 3164. 优质数对的总数 II 1777 调和级数枚举
- 2176. 统计数组中相等且可以被整除的数对 非暴力做法约 2200
- 2183. 统计可以被 K 整除的下标对数目 2246
- 952. 按公因数计算最大组件大小 2272
- 1627. 带阈值的图连通性 2221
- 2198. 单因数三元组（会员题）
- 625. 最小因式分解（会员题）
- 2847. 给定数字乘积的最小数字（会员题）
§1.6 最大公约数（GCD）
- 1979. 找出数组的最大公约数 1184
- 2807. 在链表中插入最大公约数 1279
- 914. 卡牌分组 1371
- 1071. 字符串的最大公因子 1398
- 2344. 使数组可以被整除的最少删除次数 1641
- 365. 水壶问题
- 858. 镜面反射 1881
- 2654. 使数组所有元素变成 1 的最少操作次数 1929 可以用 logTrick
- 1250. 检查「好数组」 1983 裴蜀定理
- 149. 直线上最多的点数
- 2607. 使子数组元素和相等 2071 裴蜀定理
- 2447. 最大公因数等于 K 的子数组数目 可以用 logTrick
- 2543. 判断一个点是否可以到达 2221
- 3574. 最大子数组 GCD 分数 2300 可以用 logTrick
- 3312. 查询排序后的最大公约数 2533 调和级数枚举
- 1819. 序列中不同最大公约数的数目 2540 调和级数枚举
- LCP 14. 切分数组
- 2436. 使子数组最大公约数大于一的最小分割数（会员题）
- 2464. 有效分割中的最少子数组数目（会员题）
- 2941. 子数组的最大 GCD-Sum（会员题）可以用 logTrick
§1.7 最小公倍数（LCM）
- 2413. 最小偶倍数 1145
- 3334. 数组的最大因子得分 1519
- 2197. 替换数组中的非互质数 2057
- 2470. 最小公倍数为 K 的子数组数目 log trick 做到 O(nlogk)
§1.8 互质
- 2748. 美丽下标对的数目 1301
- 1447. 最简分数 约 1400
- 1766. 互质树 2232
- 3411. 最长乘积等价子数组 非暴力做法大约 2300
§1.9 同余
- 2453. 摧毁一系列目标 1762
- 2598. 执行操作后的最大 MEX 1846
- 1590. 使数组和能被 P 整除 2039
§1.10 其他
- 326. 3 的幂
- 633. 平方数之和 费马平方和定理
- 279. 完全平方数 四平方和定理
- 1015. 可被 K 整除的最小整数 欧拉定理、欧拉函数
- 2240. 买钢笔和铅笔的方案数 类欧几里得算法
- 2221. 数组的三角和 欧拉定理/扩展卢卡斯 组合数模 10
- 3463. 判断操作后字符串中的数字是否相等 II 2286 欧拉定理/扩展卢卡斯 组合数模 10
二、组合数学
组合数取模的模板见 模运算的世界：当加减乘除遇上取模
§2.1 乘法原理
- 2125. 银行中的激光束数量 1280
- 3128. 直角三角形 1541
- 1573. 分割字符串的方案数 1591
- 2750. 将数组划分成若干好子数组的方式 1598
- 2316. 统计无向图中无法互相到达点对数 1604
- 2550. 猴子碰撞的方法数 1663
- 1922. 统计好数字的数目 1675
- 3067. 在带权树网络中统计可连接服务器对数目 1909
- 2147. 分隔长廊的方案数 1915
- 2963. 统计好分割方案的数目 1985
- 2306. 公司命名 2305
- 2867. 统计树中的合法路径数目 2428
- 1617. 统计子树中城市之间最大距离 做到 O(n3)
- 2450. 应用操作后不同二进制字符串的数量（会员题）
§2.2 组合计数
- 62. 不同路径
- 357. 统计各位数字都不同的数字个数
- 1175. 质数排列 1489
- 3179. K 秒后第 N 个元素的值 组合公式
- 1359. 有效的快递序列数目 1723
- 2400. 恰好移动 k 步到达某一位置的方法数目 1751
- 3558. 给边赋权值的方案数 I 1845
- 2514. 统计同位异构字符串数目 2070
- 3154. 到达第 K 级台阶的方案数 2071
- 1643. 第 K 条最小指令 2080
- 2842. 统计一个字符串的 k 子序列美丽值最大的数目 2092
- 3519. 统计逐位非递减的整数 2246
- 1569. 将子数组重新排序得到同一个二叉搜索树的方案数 2288
- 3405. 统计恰好有 K 个相等相邻元素的数组数目 2310
- 1866. 恰有 K 根木棍可以看到的排列数目 2333 第一类斯特林数
- 1467. 两个盒子中球的颜色数相同的概率 2357
- 3518. 最小回文排列 II 2375 试填法 多重集排列数
- 3272. 统计好整数的数目 2382
- 3317. 安排活动的方案数 2414 第二类斯特林数
- 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. 计算分配糖果的不同方式（会员题）第二类斯特林数
思维扩展：
- 3470. 全排列 IV 2474 构造，字典序第 k 小
§2.3 放球问题
- 1641. 统计字典序元音字符串的数目 1519
- 1621. 大小为 K 的不重叠线段的数目 2198
- 920. 播放列表的数量 2400
- 1735. 生成乘积数组的方案数 2500
- 2338. 统计理想数组的数目 2615
§2.4 容斥原理
部分题目有其他解法，难度分仅供参考。
- 2652. 倍数求和
- 878. 第 N 个神奇数字 1897
- 1201. 丑数 III 2039
- 2929. 给小朋友们分糖果 II
- 2930. 重新排列后包含指定子字符串的字符串数目
- 2513. 最小化两个数组中的最大值 2302
- 3116. 单面值组合的第 K 小金额 2387
- 3130. 找出所有稳定的二进制数组 II 2825
- 3336. 最大公约数相等的子序列数量 倍数容斥 莫比乌斯函数
- 2927. 给小朋友们分糖果 III（会员题）
§2.5 贡献法
- 2063. 所有子字符串中的元音 1663
- 1588. 所有奇数长度子数组的和 做到 O(n)
- 2681. 英雄的力量 2060
- 891. 子序列宽度之和 2183
- 3428. 最多 K 个元素的子序列的最值之和 这题是 891 题的进阶版本
- 3426. 所有安放棋子方案的曼哈顿距离 2443
- 2763. 所有子数组中不平衡数字之和 O(n) 做法大约 2700
思维扩展：
- 979. 在二叉树中分配硬币 1709
- 2477. 到达首都的最少油耗 2012
三、概率期望
- 1227. 飞机座位分配概率
- 688. 骑士在棋盘上的概率
- 837. 新 21 点 2350
- 1467. 两个盒子中球的颜色数相同的概率 2357
- 808. 分汤 2397
- LCR 185. 统计结果概率
- LCP 11. 期望个数统计
- 九坤-04. 筹码游戏
- 1230. 抛掷硬币（会员题）
随机情况下显著更快的算法：
四、博弈论
- 292. Nim 游戏 巴什博弈
- 1025. 除数博弈 1435
- 3227. 字符串元音游戏 1452
- 2038. 如果相邻两个颜色均相同则删除当前颜色 1468
- 877. 石子游戏 1590
- 1510. 石子游戏 IV 1787
- 486. 预测赢家
- 1690. 石子游戏 VII 1951
- 1686. 石子游戏 VI 2001
- 1927. 求和游戏 2005
- 1406. 石子游戏 III 2027
- 1140. 石子游戏 II 2035
- 1563. 石子游戏 V 2087
- 464. 我能赢吗
- 2029. 石子游戏 IX 2277
- 810. 黑板异或游戏 2341
- 1872. 石子游戏 VIII 2440
- 913. 猫和老鼠 实际约 2800
- 1728. 猫和老鼠 II 2849
- LCP 48. 无限棋局
- 294. 翻转游戏 II（会员题）
- 1908. Nim 游戏 II（会员题）
- 2005. 斐波那契树的移除子树游戏（会员题）
- 2868. 单词游戏（会员题）
五、计算几何
§5.1 点、线
- 1232. 缀点成线 1247
- 2280. 表示一个折线图的最少线段数 1681
- 1610. 可见点的最大数目 2147
- 面试题 16.03. 交点
- 面试题 16.13. 平分正方形
- 面试题 16.14. 最佳直线
- LCP 37. 最小矩形面积
- 2152. 穿过所有点的所需最少直线数量（会员题）
§5.2 圆
- 1401. 圆和矩形是否有重叠 1709
- 1453. 圆形靶内的最大飞镖数量 2202
- LCP 42. 玩具套圈
- 3235. 判断矩形的两个角落是否可达
- 1924. 安装栅栏 II（会员题）最小圆覆盖 Welzl 算法
§5.3 矩形、多边形
- 836. 矩形重叠 1443
- 223. 矩形面积
- 593. 有效的正方形
- 939. 最小面积矩形 1752
- 963. 最小面积矩形 II 1991
- 469. 凸多边形（会员题）
§5.4 凸包
六、随机算法
- 398. 随机数索引
- 382. 链表随机节点
- 384. 打乱数组
- 470. 用 Rand7() 实现 Rand10()
- 528. 按权重随机选择
- 710. 黑名单中的随机数
- 478. 在圆内随机生成点
- 497. 非重叠矩形中的随机点
- 519. 随机翻转矩阵
- 380. O(1) 时间插入、删除和获取随机元素
- 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
- 1515. 服务中心的最佳位置 梯度下降法
看上去很慢，但实际上飞快：
七、杂项
§7.1 回文数
- 9. 回文数
- 2396. 严格回文的数字 1329
- 2217. 找到指定长度的回文数 1822
- 866. 回文质数 1938
- 2967. 使数组成为等数数组的最小代价 2116
- 906. 超级回文数 2140
- 2081. k 镜像数字的和 2210
- 3260. 找出最大的 N 位 K 回文数 2370
- 3272. 统计好整数的数目 2382
- 564. 寻找最近的回文数
- 479. 最大回文数乘积
§7.2 整数拆分
- 343. 整数拆分
- 1808. 好因子的最大数目 2070
§7.3 曼哈顿距离
- 3443. K 次修改后的最大曼哈顿距离 1856
- 1131. 绝对值表达式的最大值 2059
- 3102. 最小化曼哈顿距离 2216 曼哈顿距离 → 切比雪夫距离
- 1330. 翻转子数组得到最大的数组值 2482
- 3464. 正方形上的点之间的最大距离 2806
- 1956. 感染 K 种病毒所需的最短时间（会员题）
- 2613. 美数对（会员题）
§7.4 多项式卷积
- 3549. 两个多项式相乘（会员题）FFT 模板
- 3400. 右移后的最大匹配索引数（会员题）结合根号算法
§7.5 快速沃尔什变换（FWT）
§7.6 其他
- 1523. 在区间范围内统计奇数数目 1209
- 2829. k-avoiding 数组的最小总和 1347
- 2579. 统计染色格子数 1356
- 2834. 找出美丽数组的最小和 1409
- 1414. 和为 K 的最少斐波那契数字数目 1466
- 319. 灯泡开关 约 1500
- 1780. 判断一个数字是否可以表示成三的幂的和 1506
- 3091. 执行操作使数据元素之和大于等于 K 1522
- 3468. 可行数组的数目 1545 数学推导
- 2310. 个位数字为 K 的整数之和 1559
- 2844. 生成特殊数字的最少操作 1588
- 2145. 统计隐藏数组数目 1614 数学推导
- 2541. 使数组中所有元素相等的最小操作数 II 1620
- 2195. 向数组中追加 K 个整数 1659
- 2457. 美丽整数的最小增量 1680
- 1017. 负二进制转换 1698
- 1954. 收集足够苹果的最小花园周长 1759
- 1073. 负二进制数相加 1807
- 1823. 找出游戏的获胜者 约瑟夫环
- 166. 分数到小数 有数学做法，可以不用哈希表
- 3012. 通过操作使数组长度最小 1833
- 483. 最小好进制
- 972. 相等的有理数 2121
- 1862. 向下取整数对和 2170 调和级数枚举
- 1739. 放置盒子 2198
- 2443. 反转之后的数字和 非暴力做法
- 1806. 还原排列的最少操作步数 非暴力做法
- 458. 可怜的小猪
- 60. 排列序列
- 2117. 一个区间内所有数乘积的缩写 2477
- LCP 02. 分式化简 连分数
- LCP 29. 乐团站位
- 660. 移除 9（会员题）
- 2979. 最贵的无法购买的商品（会员题）
- 2647. 把三角形染成红色（会员题）
算法题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分查找（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
如果你发现有题目可以补充进来，欢迎评论反馈。