猫史档案馆

题目描述：

辗转相处，又称欧几里得算法（gcd），用于求两个非负整数的最大公约数。

例如求1997和615的最大公约数：

1997 ÷ 615 = 3 (余 152) 615 ÷ 152 = 4(余7) 152 ÷ 7 = 21(余5) 7 ÷ 5 = 1 (余2) 5 ÷ 2 = 2 (余1) 2 ÷ 1 = 2 (余0)   以除数 和余数 反复做除法运算，当余数为 0 时，取当前算式 除数为最大公约数，得出了 1997 和 615 的最大公约数 1。     现在请你写一个程序，运用辗转相除发，求a,b的最大公约数。  

 

 

输入描述：

  包括两个非负长整数a，b  

 

 

输出描述：  

一个数：a，b的最大公约数。（这意味着末尾有一个回车符号）  

 

样例输入：  

1997 615

样例输出：

1

解题：

#include<iostream>
using namespace std;
long long gcd(long long a,long long b) //题目中要求为长整数类型，应定义为long long
{
    if(b == 0) //递归终止条件
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);  //递归
    }
}
int main() {
    long long n,m;
    cin>>n>>m;
    cout<<gcd(n,m)<<endl;
    return 0;
}