中等 · 欧几里得算法
最大公约数(GCD)
gcd(12, 18) = 6。欧几里得:gcd(a, b) = gcd(b, a mod b),直到 b 归零。还在天天服役的最古老算法。
题目
输入:一行,两个整数 a b(0 ≤ a, b ≤ 10⁹,不同时为零)。
输出:它们的最大公约数。
样例:
| 输入 | 输出 |
|---|---|
12 18 | 6 |
17 5 | 1 |
你的解答
"用我的输入试跑"的自定义输入
判题完全在你的浏览器里对隐藏测试运行。代码随打随存(本地)。Ctrl+Enter 判题。
卡住了?提示
提示 1 —— 整个算法
while (b != 0) { int t = b; b = a % b; a = t; }——结束时 a 就是答案。三行,不需要递归。
提示 2 —— 为什么成立
任何同时整除 a 和 b 的数,也整除 a mod b——所以 (a, b) 与 (b, a mod b) 共享全部公约数。第二个数收缩极快:每两轮至少减半。
解答(先自己试!)
string[] parts = Console.ReadLine().Split(' ');
int a = int.Parse(parts[0]);
int b = int.Parse(parts[1]);
while (b != 0) { int t = b; b = a % b; a = t; }
Console.WriteLine(a);欧几里得是数论的大门——LCM 只差一行:a / gcd * b。下一题:素数判定。