1627：【例 3】最大公约数

题目描述

给出两个正整数 $A,B$，求它们的最大公约数。

输入格式

输入共两行，第一行一个正整数 $A$，第二行一个正整数 $B$。

输出格式

在第一行输出一个整数，表示 $A,B$ 的最大公约数。

样例

样例输入 #1

18
24

样例输出 #1

6

样例解释 #1

$\gcd(18,24) = 6$。

数据范围

• 对于 $60\%$ 的数据，$1 \le A,B \le 10^{18}$；
• 对于 $100\%$ 的数据，$1 \le A,B \le 10^{3000}$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题中 $A,B$ 可能非常大（长达 $3000$ 位十进制数），因此不能直接用 long long 存储，也不能直接用欧几里得算法（因为取模运算涉及大数除法，较慢）。需要使用高精度计算最大公约数。

更相减损术（Stein算法）适用于高精度，因为它只涉及减法和位移，避免了取模运算。但单纯使用更相减损术可能较慢（例如 $A=10^{3000}, B=1$ 需要减很多次）。结合以下性质可以加速：

1. 如果 $A,B$ 都是偶数，则 $\gcd(A,B) = 2 \cdot \gcd(A/2, B/2)$。
2. 如果 $A$ 是偶数，$B$ 是奇数，则 $\gcd(A,B) = \gcd(A/2, B)$。
3. 如果 $A,B$ 都是奇数，则 $\gcd(A,B) = \gcd(|A-B|, \min(A,B))$。
4. 如果 $A=B$，则 $\gcd(A,B) = A$。

这样，我们可以将高精度数表示为字符串或数组，实现高精度的除以 $2$（右移）、判断奇偶性、减法、比较等操作。由于 $A,B$ 可达 $3000$ 位，操作次数不会太多（因为每次操作都会减少数值的规模）。具体步骤：

• 如果 $A=B$，返回 $A$。
• 如果 $A$ 和 $B$ 都是偶数，计数器 $cnt$ 加 $1$，$A$ 和 $B$ 都除以 $2$。
• 否则如果 $A$ 是偶数，$A$ 除以 $2$。
• 否则如果 $B$ 是偶数，$B$ 除以 $2$。
• 否则（$A,B$ 都是奇数），如果 $A>B$，则 $A = A-B$，否则 $B = B-A$。
• 重复直到 $A=B$。

最后返回 $A \times 2^{cnt}$。

注意：高精度除以 $2$ 可以通过逐位计算实现。高精度减法需要处理借位。由于 $A,B$ 可能很大，但操作次数有限，可以通过递归或循环实现。

另外，也可以使用高精度取模的欧几里得算法，但实现较复杂。更相减损术结合移位（二进制算法）更易于实现高精度。

最后输出结果，注意结果可能很大，也要用高精度输出。