求最大公约数问题

给定两个正整数，求它们的最大公约数。

输入

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

输出

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

样例输入

6 9

样例输出

3

提示

求最大公约数可以使用辗转相除法：假设 a > b > 0，那么 a 和 b 的最大公约数等于 b 和 a%b 的最大公约数，然后把 b 和 a%b 作为新一轮的输入。由于这个过程会一直递减，直到 a%b 等于 0 的时候，b 的值就是所要求的最大公约数。比如： 9 和 6 的最大公约数等于 6 和 9%6=3 的最大公约数。由于 6%3==0，所以最大公约数为 3。