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

B3634 最大公约数和最小公倍数

这道题要求我们输入两个正整数，分别求出它们的最大公约数（GCD）和最小公倍数（LCM）。

其中，最大公约数可以使用**辗转相除法（欧几里得算法）**求解，而最小公倍数则可以通过一个公式直接计算。

1. 使用辗转相除法求最大公约数

先来看一个例子：求 24 和 16 的最大公约数。

按照辗转相除法，我们可以依次计算：

16 ÷ 24 = 0，余 16
24 ÷ 16 = 1，余 8
16 ÷ 8  = 2，余 0

当余数变为 0 时，计算结束。此时最后一个非零余数，也就是最后一次除法中的除数 8，就是这两个数的最大公约数。

因此：

辗转相除法的核心其实很简单：

两个整数的最大公约数，等于其中较小的数与两数相除所得余数的最大公约数。

更一般地，可以写成：

所以，我们只需要不断用“除数和余数”替换原来的两个数，直到余数为 0。

这里还有一个小细节：两个数最初的顺序不会影响最终结果。

例如前面的 16 ÷ 24，由于被除数小于除数，得到的余数仍然是 16。下一轮就会变成 24 ÷ 16，继续正常计算。

因此，代码中不需要提前比较两个数的大小。

2. 根据最大公约数求最小公倍数

求出最大公约数后，最小公倍数就比较简单了。

因为对于两个正整数 a 和 b，有：

移项后就能得到：

例如，前面已经算出 24 和 16 的最大公约数是 8，那么它们的最小公倍数就是：

这样，我们就不需要单独编写寻找最小公倍数的算法，只要先求出最大公约数，再代入公式即可。

3. 代码实现

Python 和 C++ 采用了相同的计算原理，不过我分别使用了循环和递归两种方式实现辗转相除法。

Python 代码：

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return int(abs(a*b)/gcd(a,b))
a,b=map(int,input().split())
print(gcd(a,b),lcm(a,b))

Python 版本通过 while 循环不断更新 a 和 b。

其中：

a,b=b,a%b

利用了 Python 的多重赋值，可以同时完成两个变量的更新，而不需要额外创建临时变量。

当 b 变为 0 时，循环结束，返回 a 即可得到最大公约数。

C++ 代码：

#include<iostream>
using namespace std;
#include<cmath>
#define int long long
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b)
{
    return abs(a * b) / gcd(a, b);
}
signed main()
{
    ios::sync_with_stdio;
    cin.tie();
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << " " << lcm(a, b);
}

C++ 版本则使用递归实现 gcd()：

return b == 0 ? a : gcd(b, a % b);

这里使用了三目运算符。如果 b == 0，说明递归已经到达终止条件，直接返回 a；否则继续调用 gcd(b, a % b)。

虽然循环和递归的写法不同，但每一步执行的计算完全一样，本质上都是辗转相除法。

另外，计算最小公倍数时需要用到两个数的乘积。题目给出的两个正整数都在 int 范围内，但它们的乘积可能超出 32 位整数的表示范围，因此 C++ 版本使用了 long long。

4. 复杂度分析

辗转相除法每次都会将问题转化成规模更小的余数计算，因此求最大公约数的时间复杂度为：

求最小公倍数时，只需要调用一次最大公约数函数，再进行简单的乘除运算，所以整体时间复杂度仍然是：

空间方面，Python 的循环实现只使用了少量变量，额外空间复杂度为 O(1)。

C++ 的递归实现需要保存函数调用栈，因此空间复杂度为 O(log(min(a,b)))。

这道题最重要的就是理解辗转相除法。掌握了它之后，最大公约数可以很方便地求出，而最小公倍数也只需要代入公式即可。