刷算法题必备的数学考点汇总

在力扣刷题，「数学」是大家绕不过去的内容。力扣题库中标签为「数学」的题共有 208 道，仅次于 243 道的「动态规划」。

然而对比「动态规划」，题库中「数学」所涉及到的知识则要少很多，本篇文章将针对题库中「数学」所涉及的基础必备知识进行讲解，希望对大家日后刷题有所帮助。

基础运算

在「基础运算」部分，我们将主要介绍「位运算」与「快速幂」两个知识点。这两种运算方法难度不大，但却非常常见，属于必知必会的内容。

位运算

在计算机的世界中，一切数字都是二进制的。类比于现实世界中我们所使用的十进制，二进制即为「逢二进一」的运算体系。

我们以 B、D 来分别标记二进制与十进制，例如 10D 表示十进制中的 10，而 10B 则表示二进制中的 10。

回顾十进制，

类比十进制，进一步理解二进制：

由此我们可以发现，十进制就是「逢十进一」，而二进制就是「逢二进一」。

在计算机的运算过程中，所有的数字都是用「二进制」表示的，其中数字的每一位称为一个 bit，其取值要么为 0，要么为 1。

「位运算」是「二进制」所特有的运算，共分为 6 类，如下表所示：

我们以 1011B、0101B 举例（均为无符号数）：

1011B & 0101B = 0001B
1011B | 0101B = 1111B
1011B ^ 0101B = 1110B
~1011B = 0100B
1011B << 2 = 101100B
1011B >> 2 = 10B

想要彻底掌握位运算，还需了解原码、反码、补码等知识，但由于本文重点并不在此，因此不再详细展开。

快速幂

接下来开始介绍「快速幂」算法，该算法常用于快速指数运算。

举个例子，如果想要计算

的具体数值，最少需要计算多少次可以完成？

一个比较显然的答案是从 1 开始连乘 31 个 2，这样肯定可以得到准确的答案，但是否有更快的方法？

答案显然是「有」，如果我们用二进制来表示 31，则可以得到：

由此我们可以将

进行转化，得到：

因此我们只需要求出

，再将它们依次相乘，就可以得到

。

与此同时，

，因此我们从 1 开始只需要计算 5 次即可求出

。再将这几个数字依次乘起来，就得到了

。

这种通过将指数转化为二进制，并以此来加快幂运算的方法就是快速幂。当计算

（a 为任意实数）时，快速幂方法可以将原来的 O(x) 时间复杂度降低为 O(log(x) )，从而大大加快指数运算。

此处建议大家再手动地用快速幂计算下

的值，可进一步加深对该算法的理解。

实现该算法所需代码并不长，大家可以手动实现，也可以参考下述代码：

// 计算 a ^ bintpoww (int a, int b) {intbase = a, ans = 1;while (b) {if (b & 1) ans *= base;base *= base; b >>= 1; }return ans;}

质数

讲解完「基础运算」部分后，我们开始正式进入「数论入门知识」，该部分内容主要围绕「质数」进行展开。

首先回顾「质数」的定义：

若一个正整数无法被除了 1 和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。

根据上述定义，我们可以得知常见的质数有 2、3、5 等。另外，在整个自然数集合中，质数的数量并不多，分布也比较稀疏，对于一个足够大的整数 N，不超过 N 的质数大约有 N/ ln(N) 个。

质数判定

常见的判定质数的方式是「试除法」，假设自然数 N 不是质数，则一定存在一对数

，使得下述条件成立：

因此我们可以在

的范围内枚举 x，判断 x 是否存在。

如果 x 存在，则 N 为合数；否则 N 为质数。该算法时间复杂度为

，具体代码如下所示：

booljudgePrime(int n) {for (int i = 2; i * i <= n; i++) {if (n % i == 0) returnfalse; }returntrue;}

质数筛选

对于一个正整数 N，一次性求出 1～N 之间所有的质数，即为质数筛选。

显然根据上述「质数判定」的内容，我们可以通过枚举 1～N 的所有数，再依次使用「试除法」来判定其是否为质数，从而完成质数的筛选。但此种方法的时间复杂度过高，为

。

此处将介绍经典的「Eratosthenes 筛法」，也被称为「埃式筛」。该算法基于一个基本判断：任意质数 x 的倍数（2x,3x, …）均不是质数。

根据该基本判断，我们得到如下算法过程：

将 2～N 中所有数标记为 0
从质数 2 开始从小到大遍历 2～N 中所有自然数
如果遍历到一个标记为 0 的数 x，则将其 2～N 中 x 的所有倍数标记为 1

根据上述过程，不难发现如果一个数 x 的标记为 0，则代表这个数不是

中任何数的倍数，即 x 为质数。

接下来我们以 2～10 为例，具体过程如下所示，最终标记为橙色的数为质数：

「Eratosthenes 筛法」的时间复杂度为

，并不是最快的素数筛法，但在绝大多数的「力扣数学题」中均已够用，且其实现代码较为简单，具体如下所示：

vector<int> primes, vis;voidget_primes(int n){ vis.resize(n + 1, 0);for(int i = 2; i <= n; i++) {if(vis[i] == 0) { primes.push_back(i);for(int j = i; j <= n; j += i) vis[j] = 1; } }}

质因数分解

根据「唯一分解定理」，任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积：

其中

均为正整数，而

均为质数，且满足

。

根据上述定理，我们只需要求出所有的

，即可完成对 N 的质因数分解。

那么如何求取

呢？首先我们考虑如何求

和

。

由于

，且

为质数，因此不难发现，

是 N 所有因子中除 1 以外最小的数。

因此我们可以枚举

中的所有数 x，如果 N 是 x 的倍数，则 x 为

。得到

后，我们可以令 N 不断除以

直至其不再为

的倍数，则

等于除以

的总次数。

得到

和

后，N 去除了所有的

，因此 N 变为

。又由于

，因此我们继续枚举 x，如果再次出现 N 是 x 倍数的情况，则 x 为

。

不断使用上述算法，直至循环结束。最后还需判断 N 是否为 1，如果 N 不为 1，则

。

该算法的时间复杂度为

，具体代码如下所示，大家可以配合代码对该算法进行理解：

voiddivide(int n){vector<int> p, c;for (int i = 2; i * i <= n; i++) {if (n % i == 0) { p.push_back(i);int num = 0;while(n % i == 0) num++, n /= i; c.push_back(num); } }if (n > 1) { p.push_back(n); c.push_back(1); }}

互质判定

最后我们介绍一下如何判断两个自然数互质。

首先介绍一下「最大公约数」的概念。如果自然数 c 同时是自然数 a 和 b 的约数，即 a 和 b 同时是 c 的倍数，则 c 为 a 和 b 的公约数。

「最大公约数」就是 a 和 b 的所有公约数中最大的那一个，通常记为

。

由此我们可以得到「互质」的判定条件，如果自然数 a，b 互质，则

。

于是问题变为「如何求

？」

此处需要引入「欧几里得算法」，如下所示：

根据上述算法，可以得到如下代码，其时间复杂度为

：

intgcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

另外，再介绍一个常见的定理 ——「裴蜀定理」：

若 a,b,x,y,m 是整数，则 ax + by = m 有解当且仅当 m 是

的倍数。

该定理有一个重要的推论：整数 a,b 互质的充要条件是存在整数 x,y 使

。

习题练习

50. Pow(x, n)

题目描述

实现

，即计算 x 的 n 次幂函数。

示例 1

输入: 2.00000, 10输出: 1024.00000

示例 2

输入: 2.10000, 3输出: 9.26100

示例 3

输入: 2.00000, -2输出: 0.25000解释: 2^(-2) = (1/2)^2 = 1/4 = 0.25

说明

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是
。

解题思路

此题是快速幂的模板题，主要有两个细节需要注意：

1. n 可能为负数

2. x 可能为 0

如果 n 为负数，则

，转换一下即可。另外，由于此处出现了

，因此需要对 x = 0 的情况进行特判。

处理好上述两点后，即可使用快速幂的模板代码完成此题。

代码实现

classSolution {public:doublemyPow(double x, int n) {double ans = 1;if (x == 0) return0;if (n < 0) { n = - (n + 1); x = 1 / x; ans = x; }while (n) {if (n & 1) ans *= x; x *= x; n >>= 1; }return ans; }};

204. 计数质数

题目描述

统计所有小于非负整数 n 的质数的数量。

示例 1

输入：n = 10输出：4解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。

示例 2

输入：n = 0输出：0

示例 3

输入：n = 1输出：0

解题思路

此题为「质数筛选」的模板题，可以使用前文讲过的「Eratosthenes 筛法」通过此题，具体细节见代码。

代码实现

classSolution {public:vector<int> vis;intcountPrimes(int n){ vis.resize(n, 0);int ans = 0;for (int i = 2; i < n; i++) {if (!vis[i]) { ans++;for (int j = i; j < n; j += i) vis[j] = 1; } }return ans; }};

365. 水壶问题

题目描述

有两个容量分别为 x 升和 y 升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z 升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z 升水。

你允许：

装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1

输入: x = 3, y = 5, z = 4输出: True

示例 2

输入: x = 2, y = 6, z = 5输出: False

解题思路

观察题干中给定的三种操作，不难发现在整个过程中，两个桶都不可能同时有水且不满。

有了这个基本判断之后，我们可以发现「装满一个有水但不满的桶」是没有意义的。因为当前桶有水但不满，意味着另外一个桶要么为空，要么全满，因此如果把当前桶再变为满，则不如直接一开始就把当前桶加满。

与此同理，「清空一个有水但不满的桶」也是没有意义的，因为另一个桶非空即满。

所以我们不难发现，「装满任意一个水壶」只会让总水量增加 x 或 y,「清空任意一个水壶」只会让总水量减少 x 或 y，「从一个水壶向另一个水壶倒水」，总水量不变。

由此每次操作只会给总水量带来 x 或 y 的变化量，因此本题可以改写为：

找到一对整数 a,b，使得

，且

根据「裴蜀定理」，只要 z 是

的倍数，就一定存在一对整数 a,b 满足题意，由此本题得以顺利解决。

代码实现

classSolution {public:intgcd(int x, int y) {return y == 0 ? x : gcd(y, x%y); }boolcanMeasureWater(int x, int y, int z) {int g = gcd(x, y);if (z == 0 || (g != 0 && z % g == 0)) {if (z > x + y) return0;elsereturn1; }elsereturn0; }};

LCP 14. 切分数组

题目描述

给定一个整数数组 nums，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1。为了减少他的工作量，请求出最少可以切成多少个子数组。

示例 1

输入：nums = [2,3,3,2,3,3]输出：2

解释：最优切割为 [2,3,3,2] 和 [3,3]。第一个子数组头尾数字的最大公约数为 2，第二个子数组头尾数字的最大公约数为 3。

示例 2

输入：nums = [2,3,5,7]输出：4解释：只有一种可行的切割：[2], [3], [5], [7]

限制

解题思路

将一个数组切分为多个子数组，此类型题目常见于「动态规划」算法，因此我们用「动态规划」算法来考虑此题。

定义 f[i] 表示仅考虑前 i 个数，最少可以划分为多少个子数组。则我们可以得到如下转移方程：

注意

表示一个很大的值。

然而，上述转移方程的时间复杂度为

（考虑还需求解 gcd)，因此该方法需要进一步优化。

回顾一下之前介绍过的「唯一分解定理」：任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积：

其中

均为正整数，而

均为质数，且满足

。

由此我们可以发现，如果两个数

，则说明其唯一分解后存在相同的质数。因此我们从「质数分解」的角度入手，对上述「动态规划过程」进行进一步修改。

重新定义 f[N] 数组，以及 last，now 变量。依次遍历整个 nums 数组，假设当前遍历到的位置为 i + 1，则 f[j] 表示仅考虑前 i 个位置，存在一个位置 pos 使得 nums[pos] 的值唯一分解后存在 j 这个质数，且数组 1～(pos - 1) 最少切分的子数组个数最少。

last 表示前 i 个数最小切分的子数组个数，而 now 表示前 i + 1 个数的答案。因此假如

，令

，则如下图所示，我们可以用 f[j] + 1 来更新 now 的值。

具体更新公式如下：

last 和 now 的初值分别为 0 和 1，每遍历完一个点，令

。

遍历数组的过程中同时更新 f，last，now，最终答案为 now - 1。

至此该问题转化为「如何对数组中每个数质数分解」。

之前我们「质数分解」的复杂度为

，因此如果使用之前的「质数分解」方法，本题复杂度将变为

，无法通过。

所以我们需要对原先的质数分解算法进行优化，我们需要先求出

中每个数 k 的最小质因子

，即可将「质数分解」的复杂度降为 log(n)，具体过程如下：

于是问题进一步转化为「如何求出

中每个数 k 的最小质因子

」。

考虑之前「Eratosthenes 筛法」的过程，每一个合数都会被其所有质数标记，即：

若 k 为合数，则第一次标记 k 的质数即为
若 k 为质数，则

至此我们成功完成了此题，最终复杂度为 O(nlog(n))。

代码实现

classSolution {public:vector<int> prime, f;voidget_primes(int n){ prime.resize(n + 1, 0);for(int i = 2; i <= n; i++) {if(!prime[i]) {for(int j = i; j <= n; j += i) {if (!prime[j]) prime[j] = i; } } } }intsplitArray(vector<int>& nums){ get_primes(1e6); f.resize(1e6, 1e6); // 初始化为极大值-infint last = 0, now = 1;for(int i = 0; i < nums.size(); i++) {// 唯一分解int v = nums[i];while(v > 1) {int p = prime[v]; now = min(now, f[p] + 1); f[p] = min(f[p], last);while(v % p == 0) v /= p; } last = now, now = now + 1; }return now - 1; }};

总结

本文的总体框架如下，重点主要在于「基础运算」与「质数」部分中各算法的理解与掌握。

最后，祝大家刷题愉快！

BY /

本文作者：Gene_Liu

编辑&版式：霍霍