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>
using namespace std;

int gcd(int x, int y){
    if(y == 0) return x;
    else return gcd(y, x%y);
}

int main(){
    int a,b;
    scanf("%d%d", &a, &b);
    printf("%d", gcd(a,b));

    return 0;
}