a024. 最大公因數(GCD)

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

• 相似題：a738. 最大公约数

解法一、函式庫

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

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

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

    int a, b;
    cin >> a >> b;
    cout << __gcd(a, b);

    return 0;
}

解法二、輾轉相除法

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

✅ 完整代碼

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

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

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

    int a, b;
    cin >> a >> b;

    while(a%b != 0){
        a = a%b;
        swap(a, b);
    }
    cout << b;

    return 0;
}

解法三、窮舉

雖然是窮舉，但不是直接窮舉每個數
否則會 TLE

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

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

    int a, b;
    cin >> a >> b;

    int ans = min(a, b);
    while(true){
        if(a%ans == 0 && b%ans == 0) break;
        ans--;
    }
    cout << ans;

    return 0;
}

窮舉因數
求出較小數的所有因數後
再一一跟另一個數比對，判斷是否也是另一數的因數

✅ 完整代碼

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

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

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

    int a, b;
    cin >> a >> b;

    if(a > b) swap(a, b);
    
    vector<int> v;
    for(int i=1; i<=sqrt(a); i++){
        if(a%i == 0){
            v.push_back(i);
            v.push_back(a/i);
        } 
    }
    
    int ans = 0;
    for(int i : v){
        if(b%i == 0){
            ans = max(ans, i);
        }
    }
    
    cout << ans;

    return 0;
}