No testdata at current.

1630：SuperGCD

题目描述

Sheng Bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的 GCD（最大公约数）！因此他经常和别人比赛计算 GCD。有一天 Sheng Bill 很嚣张地找到了你，并要求和你比赛，但是输给 Sheng Bill 岂不是很丢脸！所以你决定写一个程序来教训他。

输入格式

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

输出格式

一行，表示 $A$ 和 $B$ 的最大公约数。

样例

样例输入 #1

12
54

样例输出 #1

6

样例解释 #1

$\gcd(12,54) = 6$。

数据范围

对于全部数据，$0 < A,B \le 10^{10000}$。

时空限制

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

注意：本题中 $A,B$ 是超大整数（可达 $10000$ 位十进制数），因此必须使用高精度计算最大公约数。可以使用二进制 GCD 算法（Stein算法），因为它只涉及减法和移位，避免了大数取模运算。

二进制 GCD 算法步骤（对于高精度数）：

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

需要实现高精度数的以下操作：

• 判断奇偶性：只需看最低位是否为偶数。
• 除以 $2$：高精度右移一位（即除以 $2$ 取整）。
• 比较大小：高精度比较。
• 减法：高精度减法。
• 乘法（乘以 $2$）：实际上我们不需要乘以 $2$，而是记录因子 $2$ 的个数 $cnt$，最后将结果左移 $cnt$ 位（即乘以 $2^{cnt}$）。

算法流程：

1. 初始化 $cnt = 0$。
2. 当 $A \neq B$ 时：
   • 如果 $A$ 和 $B$ 都是偶数，则 $A = A/2$，$B = B/2$，$cnt = cnt + 1$。
   • 否则如果 $A$ 是偶数，则 $A = A/2$。
   • 否则如果 $B$ 是偶数，则 $B = B/2$。
   • 否则（都是奇数），如果 $A > B$，则 $A = A - B$，否则 $B = B - A$。
3. 最后结果为 $A \times 2^{cnt}$（或 $B \times 2^{cnt}$，因为此时 $A=B$）。

由于 $A,B$ 可达 $10000$ 位，减法操作可能使得数值减小较慢，但每次操作都会减少数的规模（除以 $2$ 或减法），因此总的操作次数不会太多（大约 $O(\log(\max(A,B)))$ 次）。但高精度运算本身复杂度与位数相关，总时间复杂度可以接受。

注意：输入的数可能很大，需要用字符串读入，并转换为高精度表示（例如用数组存储十进制位，或存储二进制位）。为了方便除以 $2$，可以用十进制存储，除以 $2$ 时从高位到低位逐位计算。也可以将数转换为二进制表示（大整数转二进制），然后直接进行二进制操作，但转换可能较复杂。

由于数据规模较大，需要仔细实现高精度运算，并注意优化常数。