本文最后更新于 815 天前,其中的信息可能已经有所发展或是发生改变。
808. 最大公约数 (递归gcd()函数)
原题链接
描述
输入两个整数 a 和 b,请你编写一个函数,int gcd(int a, int b)
, 计算并输出 a 和 b 的最大公约数。
输入格式
共一行,包含两个整数 a 和 b。
输出格式
共一行,包含一个整数,表示 aa 和 bb 的最大公约数。
数据范围
1≤a,b≤1000
输入样例:
12 16
输出样例:
4
分析
- 辗转相除法求解:
欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
例如:假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
100 / 18 = 5 (余 10)
18 / 10= 1(余8)
10 / 8 = 1(余2)
8 / 2 = 4 (余0)
至此,最大公约数为2
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 100 和 18 的最大公约数2。
代码
#include <bits/stdc++.h>
using namespace std;
int gcd(int n,int m){ //递归辗转相除
if(n%m==0){
return m;
}
else return gcd(m,n%m);
}
int main()
{
int n,m;
cin>>n>>m;
cout<<gcd(n,m);
return 0;
}
扩展
- 求
n
和m
的最小公倍数,则先求n
和m
的最大公约数gcd(n,m)
,然后n*m/gcd(n,m)
则为最小公倍数。