ACM 題目解析：最小公倍數與最大公約數（山東理工大學 1181）

題目大意

輸入兩個正整數，求其最小公倍數（LCM）與最大公約數（GCD）。

輸入輸出範例

輸入：6 8
輸出：24 2

數學關係

對任意正整數 a, b：a * b = GCD(a,b) * LCM(a,b)。故可先求 GCD，再用 LCM = a*b / GCD。注意 a*b 可能溢位，建議先除後乘：LCM = a / GCD * b。

歐幾里得算法（輾轉相除法）

int gcd(int a, int b) {
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

完整程式碼

#include <stdio.h>

int main() {
    long long a, b;
    if (scanf("%lld %lld", &a, &b) != 2) return 0;
    long long x = a, y = b;
    while (y) {
        long long r = x % y;
        x = y;
        y = r;
    }
    long long gcd = x;
    long long lcm = a / gcd * b; // 先除後乘防溢位
    printf("%lld %lld\n", lcm, gcd);
    return 0;
}

原始題解碼分析

#include<stdio.h>
void main() {
    int p,r,m,n,s;
    scanf("%d%d",&n,&m);
    if(n=m
    p=m*n;
    while(m!=0) { r=n%m; n=m; m=r; } // 歐幾里得算法，結果在 n
    printf("%d %d\n",p/n,n); // p/n = m*n/gcd = lcm
}

原解邏輯正確，但變數命名 p,r,m,n,s 晦澀，且 p=m*n 可能溢位（題目測資較小故未出錯）。建議改用 long long 並先除後乘。

延伸：Stein 算法（二進制 GCD）

利用位運算加速，適合極大整數或嵌入式環境：

int gcd_stein(int u, int v) {
    if (!u || !v) return u | v;
    int shift = __builtin_ctz(u | v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u > v) { int t=v; v=u; u=t; }
        v -= u;
    } while (v);
    return u << shift;
}