该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个正整数 $a, b$ 求 $gcd(a,b)$, $gcd = greatest\ common\ divisor$ 即最大公约数

定理：

证明：

1. 设 $a \mod b = a - k \cdot b$，其中 $k = \lfloor a / b \rfloor$（向下取整）。

2. 若 $d$ 是 $(a, b)$ 的公约数：

   • 则知 $d \mid a$ 且 $d \mid b$。
   • 则易知，$d \mid (a - k \cdot b)$，即 $d$ 也是 $(b, a \mod b)$ 的公约数。

3. 若 $d$ 是 $(b, a \mod b)$ 的公约数：

   • 则知 $d \mid b$ 且 $d \mid (a - k \cdot b)$。

   • 则，$d \mid (a - k \cdot b + k \cdot b)$，即 $d \mid a$。

   • 因此，$d$ 同时整除 $a$ 和 $b$，所以 $d$ 也是 $(a, b)$ 的公约数。

4. 综上所述，$(a, b)$ 的公约数集合与 $(b, a \mod b)$ 的公约数集合相同，因此它们的最大公约数也相同。

证毕。

输入格式

第一行读入两个数字 $a, b$

输出格式

共一行，表示答案

数据范围

$1 <= n <=10^{18}$

输入样例：

3 5

输出样例：

1