问题：求最大公约数 (Greatest Common Divisor, GCD)

任务总览

题目描述

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

输入格式

• 一行 包含两个正整数 n 和 m (1 ≤ n, m ≤ 1000)，两数之间以空格分隔。

输出格式

• 输出 n 和 m 的​最大公约数​。

输入输出示例

输入示例 1

4 6

输出示例 1

2

题目分析

最大公约数（GCD，Greatest Common Divisor）是两个整数的​最大整数因子​，可以使用 辗转相除法（欧几里得算法） 快速计算：

1. 辗转相除法公式：
   • 若 m ≥ n，则 GCD(m, n) = GCD(n, m % n)，直到 n = 0，此时 m 为最大公约数。
   • 例如 GCD(4,6)：

     GCD(6, 4) -> GCD(4, 6 % 4) = GCD(4, 2)
     GCD(4, 2) -> GCD(2, 4 % 2) = GCD(2, 0)
     GCD(2, 0) -> 2 (结束)
     

   • 结果为 2。
2. 时间复杂度：
   • 欧几里得算法的时间复杂度为 O(log(min(n, m)))，对于 n, m ≤ 1000，最多 10 次计算，非常高效。

时间复杂度分析

• O(log(min(n, m)))，对于 n, m ≤ 1000，最多 10 次计算，远小于 1s 限制，完全可行。

结论

• 该问题是​基础数学问题​，可以使用辗转相除法在 O(log(min(n, m))) 时间内高效解决。