問(wèn)題描述

求兩個(gè)整數(shù)的最大公約數(shù)是一個(gè)很有價(jià)值的問(wèn)題，給定整數(shù)a和b，下面的方法可以較快速的求出a和b的最大公約數(shù)。
如果a是b的倍數(shù)，則a和b的最大公約數(shù)為b，否則a和b的最大公約數(shù)等于b和a%b的最大公約數(shù)。其中a%b表示a除b的余數(shù)。
如，要求48和72的最大公約數(shù)，用(48,72)來(lái)表示，則可以按下面的過(guò)程來(lái)求：
(48,72)=(72,48)=(48,24)=24。
給出a和b，用遞歸的方式來(lái)求a和b的最大公約數(shù)。

輸入格式

輸入的第一行包含兩個(gè)整數(shù)a, b。

輸出格式

輸出兩個(gè)數(shù)的最大公約數(shù)。

樣例輸入

48 72

樣例輸出

24

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int gcd(int a, int b)
{
if (a==0) return b;
else return gcd(b%a,a);
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}