题目描述

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法。

现在给定两个正整数，需要你编写程序求它们的最大公约数。

输入格式

输入一行，包含两个正整数 $(a, b)$，其中 $1 \leq a, b \leq 1,000,000,000$。

输出格式

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

输入样例 1

82 71

输出样例 1

1

题目说明

求最大公约数可以使用辗转相除法：

1. 假设 $a \geq 0, b = 0$，则 $a$ 和 $b$ 的最大公约数为 $a$。

2. 假设 $a \geq 0, b > 0$，那么 $a$ 和 $b$ 的最大公约数等于 $b$ 和 $a \% b$ 的最大公约数，然后把 $b$ 和 $a \% b$ 作为新一轮的输入。由于这个过程会一直递减，直到 $a \% b$ 等于 $0$ 的时候，$b$ 的值就是所要求的最大公约数。

例如：

• 9 和 6 的最大公约数等于 6 和 $(9 \% 6)$ 的最大公约数，即等于 6 和 3 的最大公约数。
• 6 和 3 的最大公约数又等于 3 和 $(6 \% 3)$ 的最大公约数，即等于 3 和 0 的最大公约数，3 和 0 的最大公约数为 3。
  因此，9 和 6 的最大公约数为 3。