题目描述

给定两个正整数 ( n ) 和 ( m )，求它们的最大公约数（GCD）。

输入输出格式

• 输入：两个整数 ( n ) 和 ( m )，满足 ( 1 \leq n, m \leq 500000 )。
• 输出：一个整数，表示 ( n ) 和 ( m ) 的最大公约数。

思路分析

最大公约数的经典解法是欧几里得算法（辗转相除法）。其核心思想是：对于两个正整数 ( a ) 和 ( b )（假设 ( a > b )），( \text{gcd}(a, b) = \text{gcd}(b, a % b) )，当 ( b = 0 ) 时，( a ) 即为最大公约数。该算法的时间复杂度为 ( O(\log \min(n, m)) )，对于 ( n, m \leq 500000 ) 的范围完全适用。

代码实现

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << gcd(n, m) << endl;
    return 0;
}

1<=n,m<=500000