【数论】求两个正整数的最大公因数与最小公倍数 - 编程导航

B3634 最大公约数和最小公倍数 - 洛谷

概念梳理：

最大公约数：两个正整数的 m、n 的最大公约数（greatest common divisor） 是指能同时整除 m 和 n 的最大因子，记为$\gcd(m, n)$。特别地，若 $\gcd(m,n)=1$，则我们称 m 和 n 互素。
最小公倍数：两个正整数 m、n 的最小公倍数（least common multiple） 是指同时被 m 和 n 整除的最小倍数，记为 $\operatorname{lcm}(m,n)$。

二者存在如下关系：

$$ m \times n = \gcd(m,n) \times \operatorname{lcm}(m,n) $$

求解 $\mathrm{lcm}(m, n)$ 的经典方法是：先求出 $\gcd(m, n)$，再利用公式： $$ \operatorname{lcm}(m,n)=\frac{m \times n}{\gcd(m,n)} $$ 计算得到。

编程实现时需要注意：直接计算 $m \times n$ 可能会导致整数溢出，因此应调整计算顺序，先做除法再做乘法，即： $$ \operatorname{lcm}(m,n)=\frac{m}{\gcd(m,n)} \times n $$

那 $\gcd(m,n)$ 又该怎么求？一个经典方法是欧几里得算法（辗转相除法）。

欧几里得算法基于一个核心结论：两个正整数的最大公约数，等于较小数与较大数除以较小数所得余数的最大公约数。

假设 $m \ge n$，上述结论可表示为： $$ \gcd(m,n)=\gcd(n,m\bmod n) $$ 因为 $m\bmod n$ 的结果 $r$ 满足 $0 \le r < n$，所以新问题 $\gcd(n,r)$ 的第二个参数严格小于原来的第二个参数 $n$。因此，每次迭代都会使问题的规模进一步缩小。

如此反复操作，直到第二个参数变为 0。此时，问题变为 $\gcd(a,0)$，其中 $a>0$。由于任意正整数都是 0 的因数，因此 $\gcd(a,0)=a$，也就是说，此时的第一个参数就是我们要求的最大公约数。

这里分别给出 gcd 方法的递归和迭代实现。考虑到迭代版的空间复杂度更低，后续将优先使用迭代版。

递归版：

▼
java
复制代码
public int gcd(int m, int n) {
    if (m < n) {
        int t = m;
        m = n;
        n = t;
    }
    if (n == 0) {
        return m;
    }
    return gcd(n, m % n);
}

时间复杂度为 $O(\log n)$，其中 $n$ 为两个输入中较小的正整数；空间复杂度为 $O(\log n)$，主要来自递归调用栈。

迭代版：

▼
java
复制代码
public int gcd(int m, int n) {
    if (m < n) {
        int t = m;
        m = n;
        n = t;
    }
    while (n > 0) {
        int r = m % n;
        m = n;
        n = r;
    }
    return m;
}

时间复杂度同上，空间复杂度 $O(1)$。

最后，便可以利用最大公约数实现 lcm 方法：

▼
java
复制代码
public long lcm(int m, int n) {
    return (long) m / gcd(m, n) * n;
}

注意：这里有两个坑点。

最小公倍数的结果可能超过 int 的最大值，因此方法的返回类型必须使用 long。

计算时需要先将 m 转换为 long。如果不进行转换，表达式 m / gcd(m, n) * n 中的操作数均为 int 类型，因此除法和最后的乘法都会以 int 类型进行计算，最后一步乘法可能发生溢出。表达式计算完成后，Java 才会将最终的 int 结果自动转换为 long 并返回，但此时溢出已经发生，类型转换也无法挽回已经溢出的结果。