刷算法题必备的基础数论知识
前言
如果你对这篇文章可感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
在力扣刷题时，「数学」是大家绕不过去的内容。事实上，力扣题库中标签为「数学」的题共有 208 道，仅次于 243 道的「动态规划」。
然而对比「动态规划」，力扣题库中「数学」所涉及到的知识则要少很多，因此本篇文章将针对题库中「数学」所涉及的基础必备知识进行讲解，希望对大家日后刷题有所帮助。
基础运算
在「基础运算」部分，我们将主要介绍「位运算」与「快速幂」两个知识点。这两种运算方法难度不大，但却非常常见，属于必知必会的内容。
位运算
在计算机的世界中，一切数字都是二进制的。类比于现实世界中我们所使用的十进制，二进制即为「逢二进一」的运算体系。
我们以 B、D 来分别标记二进制与十进制，例如 10D 表示十进制中的 10，而 10B 则表示二进制中的 10。
回顾十进制， 10 D = 1 ∗ 1 0 1 + 0 ∗ 1 0 0 10D=1*10^1+0*10^0 10D=1∗101+0∗100， 123 D = 1 ∗ 1 0 2 + 2 ∗ 1 0 1 + 3 ∗ 1 0 0 123D=1*10^2+2*10^1+3*10^0 123D=1∗102+2∗101+3∗100。
类比十进制，进一步理解二进制： 10 B = 1 ∗ 2 1 + 0 ∗ 2 0 = 2 D 10B=1*2^1+0*2^0=2D 10B=1∗21+0∗20=2D， 1011 B = 1 ∗ 2 3 + 0 ∗ 2 2 + 1 ∗ 2 1 + 1 ∗ 2 0 = 11 D 1011B=1*2^3+0*2^2+1*2^1+1*2^0=11D 1011B=1∗23+0∗22+1∗21+1∗20=11D。
由此我们可以发现，十进制就是「逢十进一」，而二进制就是「逢二进一」。
在计算机的运算过程中，所有的数字都是用「二进制」表示的，其中数字的每一位称为一个 bit，其取值要么为 0，要么为 1。
「位运算」是「二进制」所特有的运算，共分为 6 类，如下表所示：
| 运算符 | 名称 | 规则 |
|---|---|---|
| & | 与 | 两个位均为1，结果为1 |
| | | 或 | 两个位均为0，结果为0 |
| ^ | 异或 | 两个位相同则为0，不同则为1 |
| ～ | 取反 | 0变1，1变0 |
| << | 左移 | 二进制下所有位同时向左移动，低位以0填充，高位越界后舍弃 |
| >> | 右移 | 二进制下所有位同时向右移动，无符号数高位补0，有符号数则视编译器而定 |
我们以 1011B、0101B 举例（均为无符号数）：
- 1011B & 0101B = 0001B
- 1011B | 0101B = 1111B
- 1011B ^ 0101B = 1110B
- ~1011B = 0100B
- 1011B << 2 = 101100B
- 1011B >> 2 = 10B
想要彻底掌握位运算，还需了解原码、反码、补码等知识，但由于本文重点并不在此，因此不再详细展开。
快速幂
接下来开始介绍「快速幂」算法，该算法常用于快速指数运算。
举个例子，如果想要计算 2 31 2^{31} 231 的具体数值，最少需要计算多少次可以完成？
一个比较显然的答案是从 1 1 1 开始连乘 31 31 31 个 2 2 2，这样肯定可以得到准确的答案，但是否有更快的方法？
答案显然是「有」，如果我们用二进制来表示
31
31
31，则可以得到：
31
D
=
11111
B
=
1
∗
2
0
+
1
∗
2
1
+
1
∗
2
2
+
1
∗
2
3
+
1
∗
2
4
=
1
+
2
+
4
+
8
+
16
31D=11111B=1*2^0+1*2^1+1*2^2+1*2^3+1*2^4=1+2+4+8+16
31D=11111B=1∗20+1∗21+1∗22+1∗23+1∗24=1+2+4+8+16
由此我们可以将
2
31
2^{31}
231 进行转化，得到：
2
31
=
2
1
+
2
+
4
+
8
+
16
=
2
1
∗
2
2
∗
2
4
∗
2
8
∗
2
16
2^{31}=2^{1+2+4+8+16}=2^1*2^2*2^4*2^8*2^{16}
231=21+2+4+8+16=21∗22∗24∗28∗216
因此我们只需要求出 2 1 , 2 2 , 2 4 , 2 8 , 2 16 2^1,2^2,2^4,2^8,2^{16} 21,22,24,28,216，再将它们依次相乘，就可以得到 2 31 2^{31} 231。
与此同时， 2 2 = 2 1 ∗ 2 1 , 2 4 = 2 2 ∗ 2 2 , . . . , 2 16 = 2 8 ∗ 2 8 2^2=2^1*2^1,2^4=2^2*2^2,...,2^{16}=2^8*2^8 22=21∗21,24=22∗22,...,216=28∗28，因此我们从 1 1 1 开始只需要计算 5 5 5 次即可求出 2 1 , 2 2 , 2 4 , 2 8 , 2 16 2^1,2^2,2^4,2^8,2^{16} 21,22,24,28,216。再将这几个数字依次乘起来，就得到了 2 31 2^{31} 231。
这种通过将指数转化为二进制，并以此来加快幂运算的方法就是快速幂。当计算 a x a^x ax（ a a a 为任意实数）时，快速幂方法可以将原来的 O ( x ) O(x) O(x) 时间复杂度降低为 O ( l o g ( x ) ) O(log(x)) O(log(x))，从而大大加快指数运算。
此处建议大家再手动地用快速幂计算下 2 14 2^{14} 214 的值，可进一步加深对该算法的理解。
实现该算法所需代码并不长，大家可以手动实现，也可以参考下述代码：
// 计算 a ^ b
int poww (int a, int b) {
int base = a, ans = 1;
while (b) {
if (b & 1) ans *= base;
base *= base;
b >>= 1;
}
return ans;
}
质数
讲解完「基础运算」部分后，我们开始正式进入「数论入门知识」，该部分内容主要围绕「质数」进行展开。
首先回顾「质数」的定义：
若一个正整数无法被除了 1 1 1 和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该正整数为合数。
根据上述定义，我们可以得知常见的质数有 2 2 2、 3 3 3、 5 5 5 等。另外，在整个自然数集合中，质数的数量并不多，分布也比较稀疏，对于一个足够大的整数 N N N，不超过 N N N 的质数大约有 N / l n ( N ) N/ln(N) N/ln(N) 个。
质数判定
常见的判定质数的方式是「试除法」，假设自然数
N
N
N 不是质数，则一定存在一对数
x
,
y
(
x
≤
y
)
x,y(x\leq y)
x,y(x≤y)，使得下述条件成立：
N
=
x
∗
y
1
<
x
≤
N
≤
y
<
N
N=x*y \\ 1< x\leq\sqrt N\leq y<N
N=x∗y1<x≤N
≤y<N
因此我们可以在 [ 2 , N ] [2,\sqrt N] [2,N ] 的范围内枚举 x x x，判断 x x x 是否存在。
如果 x x x 存在，则 N N N 为合数；否则 N N N 为质数。该算法时间复杂度为 O ( N ) O(\sqrt N) O(N )，具体代码如下所示：
bool judgePrime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
质数筛选
对于一个正整数 N N N，一次性求出 1 ～ N 1～N 1～N 之间所有的质数，即为质数筛选。
显然根据上述「质数判定」的内容，我们可以通过枚举 1 ～ N 1～N 1～N 的所有数，再依次使用「试除法」来判定其是否为质数，从而完成质数的筛选。但此种方法的时间复杂度过高，为 O ( N N ) O(N\sqrt N) O(NN )。
此处将介绍经典的「Eratosthenes 筛法」，也被称为「埃式筛」。该算法基于一个基本判断：任意质数 x x x 的倍数（ 2 x , 3 x , . . . 2x,3x,... 2x,3x,...）均不是质数。
根据该基本判断，我们得到如下算法过程：
- 将 2 ～ N 2～N 2～N 中所有数标记为 0
- 从质数 2 2 2 开始从小到大遍历 2 ～ N 2～N 2～N 中所有自然数
- 如果遍历到一个标记为 0 的数 x x x，则将其 2 ～ N 2～N 2～N 中 x x x 的所有倍数标记为 1
根据上述过程，不难发现如果一个数 x x x 的标记为 0 0 0，则代表这个数不是 2 ～ ( x − 1 ) 2～(x-1) 2～(x−1) 中任何数的倍数，即 x x x 为质数。
接下来我们以
2
～
10
2～10
2～10 为例，具体过程如下所示，最终标记为橙色的数为质数：
「Eratosthenes 筛法」的时间复杂度为 O ( N l o g ( l o g ( N ) ) ) O(Nlog(log(N))) O(Nlog(log(N)))，并不是最快的素数筛法，但在绝大多数的「力扣数学题」中均以够用，且其实现代码较为简单，具体如下所示：
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
1
1 的正整数都能唯一分解为有限个质数的乘积：
N
=
p
1
c
1
p
2
c
2
.
.
.
p
m
c
m
N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}
N=p1c1p2c2...pmcm
其中
c
i
c_i
ci 均为正整数，而
p
i
p_i
pi 均为质数，且满足
p
1
<
p
2
<
.
.
.
<
p
m
p_1<p_2<...<p_m
p1<p2<...<pm。
根据上述定理，我们只需要求出所有的 p i , c i p_i,c_i pi,ci，即可完成对 N N N 的质因数分解。
那么如何求取 p i , c i p_i, c_i pi,ci 呢？首先我们考虑如何求 p 1 p_1 p1 和 c 1 c_1 c1。
由于 p 1 < p 2 < . . . < p m p_1<p_2<...<p_m p1<p2<...<pm，且 p 1 p_1 p1 为质数，因此不难发现， p 1 p_1 p1 是 N N N 所有因子中除 1 1 1 以外最小的数。
因此我们可以枚举 2 ～ N 2～\sqrt N 2～N 中的所有数 x x x，如果 N N N 是 x x x 的倍数，则 x x x 为 p 1 p_1 p1。得到 p 1 p_1 p1 后，我们可以令 N N N 不断除以 p 1 p_1 p1 直至其不再为 p 1 p_1 p1 的倍数，则 c 1 c_1 c1 等于除以 p 1 p_1 p1 的总次数。
得到 p 1 p_1 p1 和 c 1 c_1 c1 后， N N N 去除了所有的 p 1 p_1 p1，因此 N N N 变为 p 2 c 2 . . . p m c m p_2^{c_2}...p_m^{c_m} p2c2...pmcm。又由于 p 1 < p 2 p_1<p_2 p1<p2，因此我们继续枚举 x x x，如果再次出现 N N N 是 x x x 倍数的情况，则 x x x 为 p 2 p_2 p2。
不断使用上述算法，直至循环结束。最后还需判断 N N N 是否为 1 1 1，如果 N N N 不为 1 1 1，则 p m = N , c m = 1 p_m=N,c_m=1 pm=N,cm=1。
该算法的时间复杂度为 O ( N ) O(\sqrt N) O(N )，具体代码如下所示，大家可以配合代码对该算法进行理解：
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 c c 同时是自然数 a a a 和 b b b 的约数，即 a a a 和 b b b 同时是 c c c 的倍数，则 c c c 为 a a a 和 b b b 的公约数。
「最大公约数」就是 a a a 和 b b b 的所有公约数中最大的那一个，通常记为 g c d ( a , b ) gcd(a,b) gcd(a,b)。
由此我们可以得到「互质」的判定条件，如果自然数 a , b a,b a,b 互质，则 g c d ( a , b ) = 1 gcd(a,b)=1 gcd(a,b)=1。
于是问题变为「如何求 g c d ( a , b ) gcd(a,b) gcd(a,b) ？」
此处需要引入「欧几里得算法」，如下所示：
∀
a
,
b
∈
N
,
b
≠
0
,
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
m
o
d
b
)
\forall a,b\in \mathbb{N},b\not=0,gcd(a,b)=gcd(b,a\ mod\ b)
∀a,b∈N,b=0,gcd(a,b)=gcd(b,a mod b)
根据上述算法，可以得到如下代码，其时间复杂度为 O ( l o g ( a , b ) ) O(log(a,b)) O(log(a,b))：
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
另外，再介绍一个常见的定理 ——「裴蜀定理」：
- 若 a , b , x , y , m a,b,x,y,m a,b,x,y,m 是整数，则 a x + b y = m ax+by=m ax+by=m 有解当且仅当 m m m 是 g c d ( a , b ) gcd(a,b) gcd(a,b) 的倍数。
该定理有一个重要的推论：整数 a , b a,b a,b 互质的充要条件是存在整数 x , y x,y x,y 使 a x + b y = 1 ax+by=1 ax+by=1。
习题练习
50. Pow(x, n)
题目描述
实现 p o w ( x , n ) pow(x, n) pow(x,n)，即计算 x x x 的 n n 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 位有符号整数，其数值范围是 [ − 2 31 , 2 31 − 1 ] [−2^{31}, 2^{31} − 1] [−231,231−1]。
解题思路
此题是快速幂的模板题，主要有两个细节需要注意：
- n n n 可能为负数
- x x x 可能为 0
如果 n n n 为负数，则 x n = ( 1 x ) − n x^n=(\frac{1}{x})^{-n} xn=(x1)−n，转换一下即可。另外，由于此处出现了 1 x \frac{1}{x} x1，因此需要对 x = 0 x=0 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。
示例 2
输入：n = 0
输出：0
示例 3
输入：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
示例 2
输入: x = 2, y = 6, z = 5
输出: False
解题思路
观察题干中给定的三种操作，不难发现在整个过程中，两个桶都不可能同时有水且不满。
有了这个基本判断之后，我们可以发现「装满一个有水但不满的桶」是没有意义的。因为当前桶有水但不满，意味着另外一个桶要么为空，要么全满，因此如果把当前桶再变为满，则不如直接一开始就把当前桶加满。
与此同理，「清空一个有水但不满的桶」也是没有意义的，因为另一个桶非空即满。
所以我们不难发现，「装满任意一个水壶」只会让总水量增加 x x x 或 y y y，「清空任意一个水壶」只会让总水量减少 x x x 或 y y y，「从一个水壶向另一个水壶倒水」，总水量不变。
由此每次操作只会给总水量带来 x x x 或 y y y 的变化量，因此本题可以改写为：
- 找到一对整数 a , b a,b a,b，使得 a x + b y = z ax+by=z ax+by=z，且 z ≤ x + y z\leq x+y z≤x+y
根据「裴蜀定理」，只要 z z z 是 g c d ( x , y ) gcd(x,y) gcd(x,y) 的倍数，就一定存在一对整数 a , b a,b 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。
示例 2
输入：nums = [2,3,5,7]
输出：4
解释：只有一种可行的切割：[2], [3], [5], [7]
限制
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1\leq nums.length\leq 10^5 1≤nums.length≤105
- 2 ≤ n u m s [ i ] ≤ 1 0 6 2\leq nums[i]\leq 10^6 2≤nums[i]≤106
解题思路
将一个数组切分为多个子数组，此类型题目常见于「动态规划」算法，因此我们用「动态规划」算法来考虑此题。
定义
f
[
i
]
f[i]
f[i] 表示仅考虑前
i
i
i 个数，最少可以划分为多少个子数组。则我们可以得到如下转移方程：
f
[
i
]
=
m
i
n
(
f
[
i
]
,
f
[
j
]
+
1
)
,
满
足
g
c
d
(
n
u
m
s
[
i
]
,
n
u
m
s
[
j
+
1
]
)
>
1
f[i]=min(f[i], f[j]+1), 满足\ gcd(nums[i], nums[j+1])>1
f[i]=min(f[i],f[j]+1),满足 gcd(nums[i],nums[j+1])>1
注意
f
[
0
]
=
0
,
f
[
i
]
=
i
n
f
,
i
≥
1
f[0]=0,f[i]=inf,i\geq1
f[0]=0,f[i]=inf,i≥1，
i
n
f
inf
inf 表示一个很大的值。
然而，上述转移方程的时间复杂度为 O ( n 2 l o g ( n ) ) O(n^2log(n)) O(n2log(n))（考虑还需求解 g c d gcd gcd），因此该方法需要进一步优化。
回顾一下之前介绍过的「唯一分解定理」：任何一个大于
1
1
1 的正整数都能唯一分解为有限个质数的乘积：
N
=
p
1
c
1
p
2
c
2
.
.
.
p
m
c
m
N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}
N=p1c1p2c2...pmcm
其中
c
i
c_i
ci 均为正整数，而
p
i
p_i
pi 均为质数，且满足
p
1
<
p
2
<
.
.
.
<
p
m
p_1<p_2<...<p_m
p1<p2<...<pm。
由此我们可以发现，如果两个数 g c d ( a , b ) > 1 gcd(a, b)>1 gcd(a,b)>1，则说明其唯一分解后存在相同的质数。因此我们从「质数分解」的角度入手，对上述「动态规划过程」进行进一步修改。
重新定义 f [ N ] f[N] f[N] 数组，以及 l a s t , n o w last, now last,now 变量。依次遍历整个 n u m s nums nums 数组，假设当前遍历到的位置为 i + 1 i+1 i+1，则 f [ j ] f[j] f[j] 表示仅考虑前 i i i 个位置，存在一个位置 p o s pos pos 使得 n u m s [ p o s ] nums[pos] nums[pos] 的值唯一分解后存在 j j j 这个质数，且数组 1 ～ ( p o s − 1 ) 1～(pos-1) 1～(pos−1) 最少切分的子数组个数最少。
l
a
s
t
last
last 表示前
i
i
i 个数最小切分的子数组个数，而
n
o
w
now
now 表示前
i
+
1
i+1
i+1 个数的答案。因此假如
n
u
m
s
[
i
+
1
]
=
∏
p
i
c
i
nums[i+1]=\prod p_i^{c_i}
nums[i+1]=∏pici，令
j
=
p
i
j=p_i
j=pi，则如下图所示，我们可以用
f
[
j
]
+
1
f[j]+1
f[j]+1 来更新
n
o
w
now
now 的值。
具体更新公式如下：
n
o
w
=
m
i
n
(
n
o
w
,
f
[
p
i
]
+
1
)
f
[
p
i
]
=
m
i
n
(
f
[
p
i
]
,
l
a
s
t
)
now=min(now, f[p_i]+1) \\ f[p_i]=min(f[p_i], last)
now=min(now,f[pi]+1)f[pi]=min(f[pi],last)
l a s t last last 和 n o w now now 的初值分别为 0 0 0 和 1 1 1，每遍历完一个点，令 l a s t = n o w , n o w = n o w + 1 last=now,now=now+1 last=now,now=now+1。
遍历数组的过程中同时更新 f , l a s t , n o w f,last,now f,last,now，最终答案为 n o w − 1 now-1 now−1。
至此该问题转化为「如何对数组中每个数质数分解」。
之前我们「质数分解」的复杂度为 O ( n ) O(\sqrt n) O(n )，因此如果使用之前的「质数分解」方法，本题复杂度将变为 O ( n n ) O(n\sqrt n) O(nn )，无法通过。
所以我们需要对原先的质数分解算法进行优化，我们需要先求出 1 ～ 1 0 6 1～10^6 1～106 中每个数 k k k 的最小质因子 p r i m e [ k ] prime[k] prime[k]，即可将「质数分解」的复杂度降为 l o g ( n ) log(n) log(n)，具体过程如下：
- x = n u m s [ i ] x=nums[i] x=nums[i]
- p r i m e [ x ] prime[x] prime[x] 为当前 x x x 的最小质因子
- x = x / p r i m e [ x ] x=x/prime[x] x=x/prime[x]
- 如果 x = 1 x=1 x=1 则退出，否则回到步骤 2 2 2
于是问题进一步转化为「如何求出 1 ～ 1 0 6 1～10^6 1～106 中每个数 k k k 的最小质因子 p r i m e [ k ] prime[k] prime[k]」。
考虑之前「Eratosthenes 筛法」的过程，每一个合数都会被其所有质数标记，即：
- 若 k k k 为合数，则第一次标记 k k k 的质数即为 p r i m e [ k ] prime[k] prime[k]
- 若 k k k 为质数，则 p r i m e [ k ] = k prime[k]=k prime[k]=k
至此我们成功完成了此题，最终复杂度为 O ( n l o g ( n ) ) O(nlog(n)) 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;
}
};
总结
本文的总体框架如下，重点主要在于「基础运算」与「质数」部分中各算法的理解与掌握。
本文所介绍的算法均为力扣题库「数学」部分所涉及的基础算法，希望大家能够留个印象，在日后刷题时能及时想起。
最后祝大家刷题愉快！
推荐阅读