题目分析

本题要求计算两个超大整数（长度可达10^5位）的最大公约数（GCD）。由于输入整数远超常规数据类型的存储范围，直接使用内置运算或传统欧几里得算法会面临效率和存储的双重挑战，因此需要结合大整数处理技术和优化的GCD算法。

算法选择与原理

核心算法：二进制GCD算法（Stein算法）
传统欧几里得算法依赖取模运算，而取模在大整数场景下效率极低。二进制GCD算法通过利用整数的奇偶性优化计算，主要基于以下性质：

1. 若两个数均为偶数，则它们的GCD等于两数分别除以2后的GCD再乘以2；
2. 若一个数为偶数、另一个为奇数，则偶数除以2后，GCD不变；
3. 若两个数均为奇数，则它们的GCD等于大数减小数后的结果与小数的GCD（因两奇数之差为偶数，可继续应用上述性质简化）。

算法步骤

1. 大整数存储：将输入的字符串形式的大整数转换为数组存储，低位在前（便于后续位运算和加减操作）。例如，数字"123"存储为[3, 2, 1]（数组索引从1开始，分别对应个位、十位、百位）。

2. 提取因子2：循环检查两个数是否为偶数（通过判断个位是否为偶数）。若是偶数，则右移一位（等价于除以2），并记录共同的因子2的个数（用于最终结果修正）。

3. 处理奇数场景：当两个数均为奇数时，通过交换确保大数在前，然后用大数减去小数（结果为偶数，可继续提取因子2），重复此过程直到两数相等。

4. 结果组合：最终两数相等时的值即为奇数部分的GCD，再乘以之前记录的共同因子2的幂（通过左移操作实现），得到最终结果。

复杂度分析

• 时间复杂度：每次迭代至少会将一个数除以2或减去另一个数，使得数值规模快速缩小，整体复杂度为O((log min(a,b))²)，远优于传统欧几里得算法在大整数场景下的表现。
• 空间复杂度：O(n)，n为输入大整数的最大长度，用于存储大整数的数组。

算法标签

• 二进制GCD算法（Stein算法）
• 大整数运算
• 数论
• 高效迭代