N. 最大公约数(Hard)

给定两个正整数 $a$ 和 $b$，计算它们的最大公约数（Greatest Common Divisor, $\gcd(a,b)$）。

最大公约数是能够同时整除 $a$ 和 $b$ 的最大正整数。

输入一行，包含两个正整数 $a$ 和 $b$，用空格分隔。

输出一行，包含一个整数，表示 $a$ 和 $b$ 的最大公约数。

样例输入 1

12 18

样例输出 1

6

样例输入 2

17 19

样例输出 2

1

数据范围

• Part 1（Easy）：
  数据范围 $1 \le a,b \le 10^6$。

• Part 2（Hard）：
  数据范围 $1 \le a,b \le 10^{18}$。

提示

• 暴力法：枚举所有可能的公因子。
• 欧几里得算法：基于 $\gcd(a,b)=\gcd(b,a\bmod b)$。
• 在 C++ 中，你可能需要使用 long long 类型来存储大整数。

算法对比

思考

为什么欧几里得算法的复杂度是 $O(\log(\min(a,b)))$？什么时候得到最坏情况？