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

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

基础运算

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

位运算

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

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

回顾十进制，

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

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

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

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

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

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

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

快速幂

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

举个例子，如果想要计算 2^31 的具体数值，最少需要计算多少次可以完成？

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

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

由此我们可以将 2^31 进行转化，得到：

因此我们只需要求出

，再将它们依次相乘，就可以得到 2^31。

与此同时，

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

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

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

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

此处建议大家再手动地用快速幂计算下 2^14 的值，可进一步加深对该算法的理解。

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

// 计算 a ^ bint poww (int a, int b) {    int base = 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 为合数。该算法时间复杂度为

，具体代码如下所示：

bool judgePrime(int n) {    for (int i = 2; i * i <= n; i++) {        if (n % i == 0) return false;    }    return true;}

对于一个正整数 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;void get_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，则

该算法的时间复杂度为

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

void divide(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 互质，则

于是问题变为「如何求

？」

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

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

int gcd(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, 输入: 2.00000, 10输出: 1024.0000010输出: 1024.00000

示例 2

输入: 2.10000, 3输出: 9.26100

示例 3

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

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

1. n 可能为负数

2. x 可能为 0

如果 n 为负数，则

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

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

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

代码实现

class Solution {public:    double myPow(double x, int n) {        double ans = 1;        if (x == 0) return 0;        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。

输入：n = 0输出：0

输入：n = 1输出：0

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

代码实现

class Solution {public:    vector<int> vis;    int countPrimes(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

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

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

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

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

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

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

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

且

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

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

代码实现

class Solution {public:    int gcd(int x, int y) {        return y == 0 ? x : gcd(y, x%y);    }    bool canMeasureWater(int x, int y, int z) {        int g = gcd(x, y);        if (z == 0 || (g != 0 && z % g == 0)) {            if (z > x + y) return 0;            else return 1;        }        else return 0;    }};

LCP 14. 切分数组

题目描述

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

示例 1

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

输入：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))。

代码实现

class Solution {public:    vector<int> prime, f;    void get_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;                }            }        }    }    int splitArray(vector<int>& nums) {        get_primes(1e6);        f.resize(1e6, 1e6); // 初始化为极大值-inf        int 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;    }};

总结

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

最后，祝大家刷题愉快！

本文作者：Gene_Liu

声明：本文归 “力扣” 版权所有，未经允许禁止转载。文章封面图和文中部分图片来源于网络，如有侵权联系删除。