当前位置:首页 > 递归 > 正文
NOI2.2-7592求最大公约数问题
181+

题目大意:给定两个正整数,求它们的最大公约数(请使用辗转相除法)。

输入

输入一行,包含两个正整数(<1,000,000,000)。

输出

输出一个正整数,即这两个正整数的最大公约数。

样例输入

6 9

样例输出

3

解题思路

求最大公约数可以使用辗转相除法:如果a > b > 0,那么a和b的最大公约数等于b和a%b的最大公约数,问题会逐渐变小,直到a%b等于0的时候,b的值就是所要求的最大公约数。

比如:9和6的最大公约数等于6和9%6=3的最大公约数,由于6%3==0,所以最大公约数为3。

代码中没有判断a和b的大小,因为如果b比a大,b和a%b就自动转换成了b和a,让大的放到前面。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,

NOI2.2-7592求最大公约数问题:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter