a024.最大公因數(GCD)
a024.最大公因數(GCD) | 題目連結 : https://zerojudge.tw/ShowProblem?problemid=a024 | 解題思路 : 例如找出75 ，30的最大公因數 (1) 畫出75*30的矩形 (2)以短邊30為邊長，切割出2個30*30的正方形，矩形變成15*30 (3)以短邊15為周長，切割出2個15*15的正方形 (4)矩形無法再切割，最大公因數為15 例如找出68、30的最大公因數 (1)若x%y = 0，則y為最大公因數 (2)否則x轉成y，y轉成x%y | 程式碼 : <基礎解> /* a024. 最大公因數(GCD) skyblue https://zerojudge.tw/ShowProblem?problemid=a024 AC (2ms, 348KB) */ #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int x,y,k; while(cin >> x >> y){ while(x%y){ k = x%y; x=y; y=k; } cout << y <<"\n"; } return 0; } <遞迴解> /* a024. 最大公因數(GCD) 遞迴解 https://zerojudge.tw/ShowProblem?problemid=a024 2023/12/21 sss AC (3ms, 332KB) */ #include <bits/stdc++.h&g