题解

题目解析

给定两个正整数，求它们的最大公约数（GCD）。该问题可通过经典的欧几里得算法高效解决^[1]。

算法思路

欧几里得算法

1. 基本原理：$\gcd(a, b) = \gcd(b, a \bmod b)$ 通过递归将较大数替换为两数相除的余数，直到余数为零时，此时的非零数即为解^[2]。
2. 迭代实现：
   • 当$b \neq 0$时，计算$a \gets b$，$b \gets a \bmod b$
   • 最终$a$即为GCD

复杂度分析

• 时间复杂度：$O(\log(\min(a, b)))$ 每次迭代至少使数值减半^[3]
• 空间复杂度：$O(1)$ 仅需常数空间

正确性证明

由数论定理可知：$\gcd(a, b) = \gcd(b, a - kb)$，当取$k = \lfloor a/b \rfloor$时即为模运算形式。该过程保证数值单调递减直至收敛^[4]。

代码实现

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
  
    // 欧几里得算法核心步骤
    while (b != 0) {
        int r = a % b;  // 计算余数
        a = b;          // 替换较大数
        b = r;          // 替换较小数
    }
  
    cout << a << endl;
    return 0;
}

代码说明

1. 输入处理：读取两个正整数
2. 循环计算余数并更新数值，直到余数为零
3. 输出最终的非零数a即为结果