a738: 最大公約數

2019-08-13

內容

小海豚要上初中了，也會了一點程序設計。海豚爸爸想起大約 30 年前上高一的時候自己第一次摸電腦。現在難以想像一下那種心情，那時候一個中國大陸一個大學畢業生（很稀罕的哦）月工資只有 60 元 RMB，而一台蘋果 II 要 6000 元 RMB。海豚爸爸有生以來輸入電腦的第一個程序，就是“最大公約數”。

輸入

每行 2 個數 a, b 0 < a, b < 1000000000

EOF 結束

30 24
2 4

輸出

對每對 a,b 輸出其最大公約數

6
2

解題思路

和這題完全一樣，用輾轉相除法做。

完整程式碼

AC (2ms, 108KB)

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

int m, n;

int main()
{
    while (scanf(" %d %d", &m, &n) == 2)
    {
        while (n)
        {
            m %= n;
            SWAP(m, n);
        }
        printf("%d\n", m);
    }
    return 0;
}