题目

从标准输入读入两个正整数 a 与 b，使用 <code>while</code> 循环实现欧几里得辗转相除算法求出它们的最大公约数（GCD）；并根据公式 $\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$ 计算最小公倍数。

输入格式：一行输入两个正整数 a 和 b。

输出格式：依次输出最大公约数与最小公倍数。

数据范围与约定：1 ≤ a, b ≤ 10^9。

思路与算法

1. 辗转相除法原理
$\gcd(a, b) = \gcd(b, a \pmod{b})$，重复此过程直到余数为 0，此时的除数即为最大公约数。

2. 乘除溢出防护
计算最小公倍数时，先做除法再做乘法：lcm = (a / gcd) * b，防止两个大数相乘超出整型表示范围。

3. 内置函数 gcd 与 lcm
手写完成后，可与内置函数 gcd(a, b) 及 lcm(a, b) 对照校验。

完整程序

% Octave / MATLAB 第57题：辗转相除法求 GCD 与 LCM
[vals, count] = scanf("%d %d", 2);

if count < 2 || vals(1) <= 0 || vals(2) <= 0
    fprintf("错误：请输入两个正整数。\n");
    return;
end

orig_a = vals(1);
orig_b = vals(2);

a = orig_a;
b = orig_b;

% 辗转相除循环
while b ~= 0
    rem_val = mod(a, b);
    a = b;
    b = rem_val;
end

gcd_val = a;
% 先除后乘防止中间溢出
lcm_val = (orig_a / gcd_val) * orig_b;

fprintf("数 1: %d, 数 2: %d\n", orig_a, orig_b);
fprintf("最大公约数 GCD: %d\n", gcd_val);
fprintf("最小公倍数 LCM: %d\n", lcm_val);

运行示例

示例 1：

输入：

48 18

输出：

数 1: 48, 数 2: 18
最大公约数 GCD: 6
最小公倍数 LCM: 144

示例 2：

输入：

17 19

输出：

数 1: 17, 数 2: 19
最大公约数 GCD: 1
最小公倍数 LCM: 323