808. 最大公约数 (递归gcd()函数)
本文最后更新于 768 天前,其中的信息可能已经有所发展或是发生改变。

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;

}

扩展

  • nm的最小公倍数,则先求nm的最大公约数gcd(n,m),然后n*m/gcd(n,m)则为最小公倍数。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇