Zerojudge a024. 最大公因數(GCD)

題目連結

題意

給兩個數字 a, b，找到他們的最大公因數。

解題方法

我們用輾轉相除法的方法來解題。

兩個數字 a, b 一定可以被最大公因數整除，所以兩個數字的差也一定可以被最大公因數整除!
因此，我們可以用這個想法遞迴下去，直到一個數字等於 0，比較大的那個數字就會是最大公因數。

扣掉差的部分我們可以用餘數來快速找，因為其實取餘數就是一次減很多個直到不能再減了。
參考資料

複雜度: O(log(min(a, b)))

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a % b);
}
int main(){
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << '\n';
}

這樣的寫法，我們可以讓 b 一直都是比較小的那個數字，每次只要判斷他是不是 0 就可以了
我自己是把它背起來了，這樣就可以很快打出來！