数数论

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

字数统计: 3.6k字   |   阅读时长: 16分
, , , , ,

摘要: 本文介绍最大公约数算法的实现、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::gcd 和 std::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