a738. 最大公约数

給兩個數 a, b
計算 a, b 的最大公因數

• 相似題：a024. 最大公因數(GCD)

---

解法一、函式庫

評分結果(參考) ： AC (2ms, 332KB)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    while(cin >> a >> b){
        cout << __gcd(a, b) << "\n";
    }

    return 0;
}

---

解法二、輾轉相除法

🔹 a, b 互取餘數直到餘數 = 0

gcd(49, 28)

以 gcd(49, 28) 舉例
計算步驟如下

1. 49 % 28 = 21
2. 28 % 21 = 7
3. 21 % 7 = 0
4. gcd(49, 28) = 7

✅ 完整代碼

評分結果(參考) ： AC (2ms, 344KB)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    while(cin >> a >> b){
        while(a%b != 0){
            a = a%b;
            swap(a, b);
        }
        cout << b << "\n";
    }

    return 0;
}