d693: 最小公倍數

2019-09-03

內容

這題並不是要你算兩個數的最小公倍數，

因為大家都知道：

( from wiki )

It is too easy!

想請大家算出 n 個數的最小公倍數！

輸入

每組測試資料兩行

第一行有一整數 N ( 2 ≤ N ≤ 10 )

第二行包含 N 個正整數 ( 每個數 ≤ 100 )

當 N 為 0 時請結束程式

2
3 5
0

輸出

每組測試資料輸出一行

請輸出 N 個正整數的最小公倍數

答案保證小於 2³¹-1

15

解題思路

最大公因數可以用輾轉相除法求得，最小公倍數則將兩數相乘去除以最大公因數即可。

lcm = (n * m) / gcd(n, m)

先求前兩數的 lcm，接下來重複和下一個讀取到的值求 lcm 直到結束後輸出 lcm 即可。

注意！題目雖然保證答案必在 int 範圍內但 n 和 m 相乘時式有機會超過的，所以要用 long long。

完整程式碼

AC (2ms, 108KB)

#include <stdio.h>
#define SWAP(x, y) (x)^=((y)^=((x)^=(y)))

inline int lcm(long long m, int n)
{
    long long res = m * n;
    while (n)
    {
        m %= n;
        SWAP(m, n);
    }
    return res / m;
}

int main()
{
    int n, ans, tmp;
    while (scanf(" %d %d", &n, &ans) == 2 && n)
    {
        while (--n)
        {
            scanf(" %d", &tmp);
            ans = lcm(ans, tmp);
        }
        printf("%d\n", ans);
    }
    return 0;
}