4172: §2 4 求最大公约数问题
[Creator : ]
Description
给定两个正整数，求它们的最大公约数。
Input
输入一行，包含两个正整数 $n,\ m\ (1 \leq n,\ m<1,000,000,000)$。
Output
输出一个正整数，即这两个正整数的最大公约数。
Sample 1 Input
6 9
Sample 1 Output
3
Sample 2 Input
4 16
Sample 2 Output
4
Sample 3 Input
1000 1001
Sample 3 Output
1
HINT
求最大公约数可以使用辗转相除法：
假设 $a > b > 0$，那么 $a,b$ 的最大公约数等于 $b$ 和 $a\bmod b$ 的最大公约数，然后把 $b$ 和 $a \bmod b$ 作为新一轮的输入。
由于这个过程会一直递减，直到 $a \bmod b$ 等于 $0$ 的时候，$b$ 的值就是所要求的最大公约数。
比如：
$9$ 和 $6$ 的最大公约数等于 $6$ 和 $9 \bmod 6=3$ 的最大公约数。
由于 $6 \bmod 3 \equiv 0$，所以最大公约数为 $3$。
假设 $a > b > 0$，那么 $a,b$ 的最大公约数等于 $b$ 和 $a\bmod b$ 的最大公约数，然后把 $b$ 和 $a \bmod b$ 作为新一轮的输入。
由于这个过程会一直递减，直到 $a \bmod b$ 等于 $0$ 的时候，$b$ 的值就是所要求的最大公约数。
比如：
$9$ 和 $6$ 的最大公约数等于 $6$ 和 $9 \bmod 6=3$ 的最大公约数。
由于 $6 \bmod 3 \equiv 0$，所以最大公约数为 $3$。