中等 · 歐幾里得演算法
最大公約數(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。下一題:素數判定。