题目

从标准输入读入两个正整数 a 和 b，计算并输出它们的最小公倍数（LCM）。

输入格式：一行输入两个正整数 a 和 b，以空格分隔。数据范围：1 ≤ a, b ≤ 109。

输出格式：输出一个整数，表示 a 和 b 的最小公倍数，末尾输出换行。

思路与算法

1. 数学原理
两个正整数 a 和 b 的最大公约数记为 gcd(a, b)，最小公倍数记为 lcm(a, b)。由数论性质可知，两数之积等于它们最大公约数与最小公倍数的乘积，即：
a × b = gcd(a, b) × lcm(a, b)
由此推导最小公倍数的计算公式为：
lcm(a, b) = (a × b) / gcd(a, b)

2. 核心考点：运算顺序与防溢出
如果代码中直接计算 (a * b) / gcd，当两个数都在 105 左右时，乘积 a * b 会达到 1010，超出 32 位有符号整型 int 的上限（约 2.14×109），导致溢出错误。
因为 gcd 是 a 的公因数，a / gcd 一定能整除。所以应当先除后乘：
(long long)a / gcd * b
先除法后乘法既不会损失精度，又能有效控制计算的中间数值，避免溢出。同时使用 long long 保存计算结果。

3. 辗转相除法求 GCD
求解最大公约数使用欧几里得算法（辗转相除法）：gcd(a, b) = gcd(b, a % b)，重复取余直到余数为 0，此时的除数就是最大公约数。单次计算的时间复杂度为 O(log(min(a, b)))。

完整程序

#include <stdio.h>

/**
 * 辗转相除法求两数最大公约数（欧几里得算法）
 */
static long long gcd(long long a, long long b)
{
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main(void)
{
    long long a, b;

    // 读入两数并校验是否为正整数
    if (scanf("%lld %lld", &a, &b) != 2 || a <= 0 || b <= 0) {
        return 1;
    }

    // 先求出最大公约数
    long long g = gcd(a, b);

    // 关键技巧：先除以 g 再乘 b，防止 a * b 中间结果溢出
    long long lcm = (a / g) * b;

    // 输出最小公倍数
    printf("%lld\n", lcm);

    return 0;
}

运行示例

示例 1（常规数值）：

输入：

4 6

输出：

12

示例 2（较大数值）：

输入：

150000 250000

输出：

750000

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

写法一：递归求最大公约数

欧几里得算法写成递归形式代码更短，递归深度通常在几十次以内，调用栈开销极小。

#include <stdio.h>

// 递归求最大公约数：b 为 0 时递归终止
static long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main(void)
{
    long long a, b;
    if (scanf("%lld %lld", &a, &b) != 2 || a <= 0 || b <= 0) {
        return 1;
    }

    // 先除后乘，避免溢出
    long long lcm = (a / gcd(a, b)) * b;
    printf("%lld\n", lcm);

    return 0;
}

写法二：定义法枚举（仅适合极小数值）

从较大数 max(a, b) 开始，每次累加一个该数值的步长，直到找到第一个能同时整除 a 和 b 的数。
说明：该方法的时间复杂度取决于最小公倍数的大小，数值较大或两数互质时循环次数极大，容易超时，仅用于理解最小公倍数的数学定义。

#include <stdio.h>

int main(void)
{
    long long a, b;
    if (scanf("%lld %lld", &a, &b) != 2 || a <= 0 || b <= 0) {
        return 1;
    }

    // 以两数中的较大值为步长累加
    long long step = (a > b) ? a : b;
    long long m = step;

    while (m % a != 0 || m % b != 0) {
        m += step;
    }

    printf("%lld\n", m);
    return 0;
}