24. 裴蜀定理

在数论中，裴蜀定理（裴蜀等式/贝祖定理）是一个关于最大公约数的定理。

对任何整数 \(a\) 、\(b\) 和 \(m\) ，关于未知数 \(x\) 和 \(y\) 的不定方程（解只能是整数）：

\[ax + by = m\]

有整数解当且仅当 \(m\) 是 \(a\) 和 \(b\) 的最大公约数的倍数。

裴蜀等式有解时必然有无穷多个整数解，每组解 \(x\) 和 \(y\) 都称为裴蜀数，可用 扩展欧几里得算法 求得。

裴蜀等式也可以用来给最大公约数定义：最小的可以写成 \(ax + by\) 形式的正整数。

特别地，方程 \(ax + by = 1\) 有解当且仅当 \(a\) 和 \(b\) 互质（最大公约数是 1）。

24.1. 最大公约数

设 \(a \geq b\) 且均为正整数，其最大公约数（Greatest Common Divisor）性质如下：

  • \(\gcd(a, b) = \gcd(b, a)\)

  • \(\gcd(a, b) = \gcd(a\%b, b)\)

  • \(\gcd(a, b) = \gcd(a-b, b)\)

  • 当 \(a\) 和 \(b\) 都是偶数时，\(\gcd(a, b) = 2 \times \gcd(a/2, b/2)\)

  • 当 \(a\) 是偶数、 \(b\) 是奇数时，\(\gcd(a, b) = \gcd(a/2, b)\)

  • 当 \(a\) 是奇数、 \(b\) 是偶数时，\(\gcd(a, b) = \gcd(a, b/2)\)

辗转相除法《几何原本》

取模运算比较耗时。

 1int gcd(int a, int b)
 2{
 3    if (a < b) swap(a, b);
 4    int r;
 5    while (r = a % b)
 6    {
 7        a = b;
 8        b = r;
 9    }
10    return b;
11}

更相减损术 《九章算术》

当两个数相差较大时，递归比较深。

1int gcd(int a, int b)
2{
3    if(a == b) return a;
4    if(a > b) return gcd(a-b, b);
5    else return gcd(a, b-a);
6}

Binary GCD Algorithm

使用移位运算和减法代替除法。

1int gcd(int a, int b)
2{
3    if(a == b) return a;
4    if(!(a&1) && !(b&1)) return 2 * gcd(a>>1, b>>1);
5    else if(!(a&1)) return gcd(a>>1, b);
6    else if(!(b&1)) return gcd(a, b>>1);
7    else return a > b? gcd(a-b, b): gcd(a, b-a);
8}

24.2. 最小公倍数

最小公倍数（Least Common Multiple）是能同时被给定的多个整数整除的最小正整数。

最小公倍数和最大公约数满足：

\[\gcd(a,b) \times \mathrm{lcm}(a,b) = | a \times b|\]

Tip

Python 库函数： math.gcd math.lcm

C++ 库函数： std::gcd std::lcm （C++ 17 标准，头文件 <numeric> ）

24.3. 质因数分解

 1## 不断除以 2 之后，2 的倍数都不可能再整除 n；3,5,7,... 同理。
 2## 思想类似于：找到 n 以内的素数，即把素数的倍数都排除。
 3def decomp(n):
 4    ans = []
 5    prime = 2
 6    while n >= prime:
 7        if n % prime == 0:
 8            ans.append(prime)
 9            n /= prime
10        else:
11            prime += 1
12  return ans

24.4. 水壶问题

https://leetcode.com/problems/water-and-jug-problem

判断用两个水壶能否量出指定体积的水。

1import math
2class Solution:
3    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
4        if jug1Capacity + jug2Capacity < targetCapacity:
5            return False
6        if jug1Capacity == 0 or jug2Capacity == 0:
7            return targetCapacity in [0, jug1Capacity + jug2Capacity]
8        return targetCapacity % math.gcd(jug1Capacity, jug2Capacity) == 0

24.5. 参考资料

  1. 裴蜀定理

  1. 最大公约数

  1. Greatest common divisor