P10518: 递归法求最大公约数
传统题
1.000s
时间限制
256MB
内存限制
35 提交
22 解决
【题目描述】
两个正整数的最大公约数是能够整除这两个整数的最大整数。采用递归方法编写计算最大公约数的函数
Gcd()，在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。
递归方法：对正整数
a和b，当a>b时，若a中含有与b相同的公约数，则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数，对a-b和b计算公约数就相当于对a和b计算公约数。反复使用最大公约数的如下3条性质，直到a和b相等为止，这时，a或b就是它们的最大公约数。
性质
1：如果a>b，则a和b与a-b和b的最大公约数相同，即Gcd（a，b）=Gcd（a-b，b）
性质
2：如果b>a，则a和b与a和b-a的最大公约数相同，即Gcd（a，b）=Gcd（a，b-a）
性质
3：如果a=b，则a和b的最大公约数与a值和b值相同，即Gcd（a，b）=a=b
【输入】
2个正整数。两数之间用逗号隔开。
【输出】
1个数。这个数是最大公约数。