最大公约数算法以及C++17组件

  |  

摘要: 本文介绍最大公约数算法的实现、C++17 相应的组件、以及几道相关题目

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


最大公约数是数论中最基础的内容,在算法中也经常见到关于最大公约数相关的问题。本文首先介绍一下最大公约数的算法实现,以及 C++17 中可以直接用的组件,并系统梳理一下相关的题目,内容总览如下:

$1 最大公约数的实现

算法:欧几里得算法(辗转相除法)

  • 递归
1
2
3
4
5
6
ll gcd(ll a,ll b)
{
if(b == 0)
return a;
return gcd(b, a % b);
}
  • 非递归
1
2
3
4
5
6
7
8
9
10
ll gcd2(ll x, ll y)
{
while (y != 0)
{
ll t = x % y;
x = y;
y = t;
}
return x;
}
  • 最小公倍数
1
2
3
4
ll lcm(ll x, ll y)
{
return x * y / gcd(x, y);
}

欧几里得算法的时间复杂度 $O(\log(a+b))$

算法流程如下:

1
gcd(a, b) = gcd(b, a % b)   b!=0

记 $m = a % b$,有 $m < a / 2$。下面看 b 的情况:

如果 $b < a / 2$,则 $m < b < a / 2$;否则 $m < a - b < a / 2$

迭代一次后 $b \rightarrow a$, $m \rightarrow b$, 两次迭代会使得余数变为被除数($m \rightarrow a$),即两次迭代会使得 a 至少会变为原来的一半。

因此总时间复杂度 $O(\log(a + b))$。


$2 std::gcdstd::lcm

C++17 中由 <numeric> 引入。

$3 题目

1201. 丑数 III

给你四个整数:n 、a 、b 、c ,请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

提示:

1
2
3
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内

示例 1:
输入:n = 3, a = 2, b = 3, c = 5
输出:4
解释:丑数序列为 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 个是 4。

示例 2:
输入:n = 4, a = 2, b = 3, c = 4
输出:6
解释:丑数序列为 2, 3, 4, 6, 8, 9, 10, 12… 其中第 4 个是 6。

示例 3:
输入:n = 5, a = 2, b = 11, c = 13
输出:10
解释:丑数序列为 2, 4, 6, 8, 10, 11, 12, 13… 其中第 5 个是 10。

示例 4:
输入:n = 1000000000, a = 2, b = 217983653, c = 336916467
输出:1999999984

算法: 最小公倍数 + 值域二分 + 容斥原理

直接找第 n 个丑数比较难。而小于等于 k 的丑数有多少个这个问题相对简单。

因此可以使用值域二分,对于 mid,我们求出小于等于 mid 的丑数的个数 c。如果 c < n,则答案大于 mid,否则答案小于等于 mid。

小于等于 k 的丑数有多少个,这个问题可以通过容斥原理解决,具体看代码中的 check 函数即可。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
int left = 1;
int right = INT_MAX;
while(left < right)
{
int mid = left + (right - left) / 2;
int k = check(a, b, c, mid);
if(k < n)
left = mid + 1;
else
right = mid;
}
return left;
}

private:
using ll = long long;

int check(int a, int b, int c, int k)
{
// <= k 的丑数有多少个
return k / a + k / b + k / c - k / lcm<ll>(a, b) - k / lcm<ll>(a, c) - k / lcm<ll>(b, c) + k / lcm<ll>(lcm<ll>(a, b), c);
}
};

365. 水壶问题

有两个水壶,容量分别为 jug1Capacity 和 jug2Capacity 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 targetCapacity 升。

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

你可以:

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

提示:

1
1 <= jug1Capacity, jug2Capacity, targetCapacity <= 1e6

示例 1:
输入: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4
输出: true
解释:来自著名的 “Die Hard”

示例 2:
输入: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5
输出: false

示例 3:
输入: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3
输出: true

算法: 裴蜀定理

详细题解参考 力扣365-水壶问题,BFS,裴蜀定理

裴蜀定理如下:

对任何整数 a、b和它们的最大公约数 d ,关于未知数 x 和 y 的线性丢番图方程(线性不定方程),若 a, b 是整数, 且 gcd(a,b)=d,那么对于任意的整数 x, y, ax+by 都一定是 d 的倍数,特别地,一定存在整数 x, y,使 ax + by = d 成立。

重要推论:

推论是:a,b 互质的充要条件是存在整数 x,y 使 ax+by=1.

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if(z ==0) return true;
if(x == y && y == 0) return false;
if(x == 0 && y != z) return false;
if(y == 0 && x != z) return false;
if(x + y < z) return false;
return z % gcd<int>(x, y) == 0;
}
};

914. 卡牌分组

给定一副牌,每张牌上都写着一个整数。

此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组:

  • 每组都有 X 张牌。
  • 组内所有的牌上都写着相同的整数。
  • 仅当你可选的 X >= 2 时返回 true。

提示:

1
2
1 <= deck.length <= 1e4
0 <= deck[i] < 1e4

示例 1:
输入:deck = [1,2,3,4,4,3,2,1]
输出:true
解释:可行的分组是 [1,1],[2,2],[3,3],[4,4]

示例 2:
输入:deck = [1,1,1,2,2,2,3,3]
输出:false
解释:没有满足要求的分组。

算法1: 最大公约数

记 cnt[x] 表示一副牌中 x 出现的次数。如果 cnt 数组的所有元素的最大公约数大于等于 2,那么就可以实现分组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
int n = deck.size();
if(n == 1)
return false;
vector<int> cnt(1e4, 0);
for(int num: deck)
++cnt[num];
vector<int> vec;
for(int i: cnt)
{
if(i != 0)
vec.push_back(i);
}
int m = vec.size();
if(m == 1)
return true;
int min_gcd = gcd<int>(vec[0], vec[1]);
if(min_gcd < 2)
return false;
for(int i = 2; i < m; ++i)
{
min_gcd = gcd<int>(min_gcd, vec[i]);
if(min_gcd < 2)
return false;
}
return true;
}
};

算法2: 素数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
vector<int> get_primes(int n) {
if(n < 2) return {};
vector<bool> vec(n, true);
vec[0] = false;
vec[1] = false;
int cnt = 0;
vector<int> primes;
for(int i = 2; i < n; ++i)
{
if(vec[i])
{
++cnt;
primes.push_back(i);
}
for(int j = 0; j < cnt && i * primes[j] < n; ++j)
{
vec[i * primes[j]] = false;
if(i % primes[j] == 0)
break;
}
}
return primes;
}

class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
int n = deck.size();
if(n == 1) return false;
vector<int> cnt(1e4, 0);
for(int num: deck)
++cnt[num];
vector<int> vec;
int minx = INT_MAX;
for(int i: cnt)
{
if(i != 0)
vec.push_back(i);
if(i > 0)
minx = min(minx, i);
}
vector<int> primes = get_primes(minx + 1);
for(int prime: primes)
{
bool flag = true;
for(int num: vec)
if(num % prime != 0)
{
flag = false;
break;
}
if(flag) return true;
}
return false;
}
};

189. 旋转数组

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示:

1
2
3
1 <= nums.length <= 1e5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 1e5

进阶:

尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

算法1: 最大公约数

nums[0] 开始,放到该数的新位置 (0 + k),然后再寻找该位置值的新位置,直至回到 0 结束。

但是该方法不能保证一次遍历就完成所有的位置,需要多次遍历。通过推导可以得到遍历的次数就是数组长度和 k 的最大公约数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
for (int i = 0; i < gcd<int>(k, len); ++i)
{
int idx = (k + i) % len;
int num = nums[i];
while (idx != i)
{
int item = nums[idx];
nums[idx] = num;
idx = (idx + k) % len;
num = item;
}
nums[i] = num;
}
}
};

算法2: reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.empty()) return;
int n = nums.size();
k %= n;
_reverse(nums, 0, n - 1);
_reverse(nums, 0, k - 1);
_reverse(nums, k, n - 1);
}

private:
void _reverse(vector<int>& nums, int left, int right)
{
while(left < right)
{
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
++left;
--right;
}
}
};

算法3: std::rotate

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.empty())
return;
int n = nums.size();
k %= n;
std::rotate(nums.begin(), nums.end() - k, nums.end());
}
};

592. 分数加减运算

给定一个表示分数加减运算的字符串 expression ,你需要返回一个字符串形式的计算结果。

这个结果应该是不可约分的分数,即最简分数。 如果最终结果是一个整数,例如 2,你需要将它转换成分数形式,其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

提示:

1
2
3
4
5
输入和输出字符串只包含 '0' 到 '9' 的数字,以及 '/', '+' 和 '-'。 
输入和输出分数格式均为 ±分子/分母。如果输入的第一个分数或者输出的分数是正数,则 '+' 会被省略掉。
输入只包含合法的最简分数,每个分数的分子与分母的范围是 [1,10]。 如果分母是1,意味着这个分数实际上是一个整数。
输入的分数个数范围是 [1,10]。
最终结果的分子与分母保证是 32 位整数范围内的有效整数。

示例 1:
输入: expression = “-1/2+1/2”
输出: “0/1”

示例 2:
输入: expression = “-1/2+1/2+1/3”
输出: “1/3”

示例 3:
输入: expression = “1/3-1/2”
输出: “-1/6”

算法: 最大公约数 + 最小公倍数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
string fractionAddition(string expression) {
if(expression.empty()) return "";
vector<int> A, B;
if(expression[0] != '-')
expression = '+' + expression;
int n = expression.size();
int i = 0;
while(i < n)
{
int j = i;
while(j < n && expression[j] != '/')
++j;
stringstream ss;
int a;
ss << expression.substr(i , j - i);
ss >> a;
A.push_back(a);
i = j + 1;
j = i;
while(j < n && expression[j] >= '0' && expression[j] <= '9')
++j;
ss.clear();
ss << expression.substr(i, j - i);
int b;
ss >> b;
B.push_back(b);
i = j;
}
int m = B.size();
int b = 1;
int a = 0;
for(int i = 0; i < m; ++i)
b = lcm<int>(b, B[i]);
for(int i = 0; i < m; ++i)
a += A[i] * b / B[i];
int t = gcd<int>(a, b);
a /= t;
b /= t;
string result;
result += to_string(a) + '/' + to_string(b);
return result;
}
};

1071. 字符串的最大公因子

对于字符串 s 和 t,只有在 s = t + … + t(t 自身连接 1 次或多次)时,我们才认定 “t 能除尽 s”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x,要求满足 x 能除尽 str1 且 X 能除尽 str2 。

提示:

1
2
1 <= str1.length, str2.length <= 1000
str1 和 str2 由大写英文字母组成

示例 1:
输入:str1 = “ABCABC”, str2 = “ABC”
输出:”ABC”

示例 2:
输入:str1 = “ABABAB”, str2 = “ABAB”
输出:”AB”

示例 3:
输入:str1 = “LEET”, str2 = “CODE”
输出:””

算法: 最大公约数

要求 x 既能除尽 str1,也能除尽 str2。记 x 长度为 l,str1 长度为 n, str2 长度为 m。

那么需要满足 l 既能整除 n 又能整除 m。也就是 l 是 n 和 m 的公约数。下面我们看一下 l 是否为 n 和 m 的最大公约数。

如果 l 不为 n 和 m 的最大公约数,但是 x 满足连接 k1 次得到 str1,连接 k2 次得到 str2。

假设 n 和 m 的最大公约数为 gcd(n, m),假设这个最大公约数乘以 k1, k2 可以分别得到 n, m:

1
2
n = k1 * gcd(n, m)
m = k2 * gcd(n, m)

又因为 gcd(n, m) 是 l 的整数倍,假设为 k 倍:gcd(n, m) = l * k,那么:

1
2
n = k1 * k * l
m = k2 * k * l

因此如果 x 既能除尽 str1,也能除尽 str2,那么将 x 复制 k 倍形成最大公约数长度,也可以分别除尽 str1 和 str2。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
string gcdOfStrings(string str1, string str2) {
int n = str1.size(), m = str2.size();
int l = gcd<int>(n, m);
string X = str1.substr(0, l);
int i = 0;
while(i < n)
{
string cur = str1.substr(i, l);
if(cur != X)
return "";
i += l;
}
i = 0;
while(i < m)
{
string cur = str2.substr(i, l);
if(cur != X)
return "";
i += l;
}
return X;
}
};

1447. 最简分数

给你一个整数 n ,请你返回所有 0 到 1 之间(不包括 0 和 1)满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。

提示:

1
1 <= n <= 100

示例 1:
输入:n = 2
输出:[“1/2”]
解释:”1/2” 是唯一一个分母小于等于 2 的最简分数。

示例 2:
输入:n = 3
输出:[“1/2”,”1/3”,”2/3”]

示例 3:
输入:n = 4
输出:[“1/2”,”1/3”,”1/4”,”2/3”,”3/4”]
解释:”2/4” 不是最简分数,因为它可以化简为 “1/2” 。

示例 4:
输入:n = 1
输出:[]

算法: 最大公约数

枚举所有可能得分子分母组合,判断它们的最大公约数是否为 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<string> simplifiedFractions(int n) {
vector<string> result;
for(int b = 2; b <= n; ++b)
{
for(int a = 1; a < b; ++a)
{
if(gcd<int>(a, b) == 1)
{
result.push_back(to_string(a) + '/' + to_string(b));
}
}
}
return result;
}
};

Share