12775: 【设计型】第7章:函数7.7(3) 递归法求最大公约数

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:1

Description

两个正整数的最大公约数是能够整除这两个整数的最大整数。采用递归方法编写计算最大公约数的函数Gcd(),在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。

递归方法:对正整数ab,当a>b时,若a中含有与b相同的公约数,则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数,对a-bb计算公约数就相当于对ab计算公约数。反复使用最大公约数的如下3条性质,直到ab相等为止,这时,ab就是它们的最大公约数。

 性质1:如果a>b,则aba-bb的最大公约数相同,即Gcdab=Gcda-bb

 性质2:如果b>a,则abab-a的最大公约数相同,即Gcdab=Gcdab-a

 性质3:如果a=b,则ab的最大公约数与a值和b值相同,即Gcdab=a=b



Input

2个正整数。两数之间用逗号隔开。

Output

1个数。这个数是最大公约数。

Sample Input Copy

50,15

Sample Output Copy

5