#4184. 求最大公约数 (Greatest Common Divisor, GCD)
求最大公约数 (Greatest Common Divisor, GCD)
问题:求最大公约数 (Greatest Common Divisor, GCD)
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
求最大公约数 | 1s | 1024 KiB | 50 |
题目描述
给定两个正整数 n
和 m
,计算它们的最大公约数 (GCD)。
输入格式
- 一行 包含两个正整数
n
和m
(1 ≤ n, m ≤ 1000
),两数之间以空格分隔。
输出格式
- 输出
n
和m
的最大公约数。
输入输出示例
输入示例 1
4 6
输出示例 1
2
题目分析
最大公约数(GCD,Greatest Common Divisor)是两个整数的最大整数因子,可以使用 辗转相除法(欧几里得算法) 快速计算:
- 辗转相除法公式:
- 若
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
。
- 若
- 时间复杂度:
- 欧几里得算法的时间复杂度为
O(log(min(n, m)))
,对于n, m ≤ 1000
,最多10
次计算,非常高效。
- 欧几里得算法的时间复杂度为
时间复杂度分析
O(log(min(n, m)))
,对于n, m ≤ 1000
,最多10
次计算,远小于1s
限制,完全可行。
结论
- 该问题是基础数学问题,可以使用辗转相除法在
O(log(min(n, m)))
时间内高效解决。