#4184. 求最大公约数 (Greatest Common Divisor, GCD)

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

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


任务总览

任务名称 时间限制 内存限制 分数
求最大公约数 1s 1024 KiB 50

题目描述

给定两个正整数 nm,计算它们的最大公约数 (GCD)。


输入格式

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

输出格式

  • 输出 nm 的​最大公约数​。

输入输出示例

输入示例 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))) 时间内高效解决。