輸入兩個正整數 m, n，求最大公約數 (GCD) 與最小公倍數 (LCM)。原帖嘗試用遞減遍歷法，存在邏輯缺陷 (邊界錯誤、break 位置、無法處理大數)。
原理：
gcd(a, b) = gcd(b, a % b)，直到餘數為 0，當前除數即為 GCD。
LCM 公式：lcm(a, b) = a / gcd(a, b) * b(先除後乘防溢出)。
#include <stdio.h>
long long gcd_iter(long long a, long long b) {
long long r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
long long m, n;
printf("輸入兩個正整數: ");
if (scanf("%lld %lld", &m, &n) != 2 || m <= 0 || n <= 0) {
printf("輸入無效\n");
return 1;
}
long long g = gcd_iter(m, n);
long long l = m / g * n; // 先除後乘，避免 m*n 溢出
printf("最大公約數 (GCD) = %lld\n", g);
printf("最小公倍數 (LCM) = %lld\n", l);
return 0;
}long long gcd_rec(long long a, long long b) {
if (b == 0) return a;
return gcd_rec(b, a % b);
}| 缺陷 | 原代碼表現 | 後果 | 輾轉相除法優勢 |
|---|---|---|---|
| 邊界條件錯誤 | k = n-1 或 m-1，忽略兩數相等情況 | 輸入相同數 (如 6,6) 時漏算 GCD=6 | 自然處理相等情況 (餘數 0 直接返回) |
| break 位置導致邏輯錯誤 | if(...) printf; break; 放在 if 內部 | 若第一次不滿足條件，循環繼續；滿足時 break 跳出，但未處理未找到情況 | 循環條件 b!=0 自然終止，邏輯清晰 |
| 時間複雜度高 | O(min(m,n))，大數 (10⁹) 需 10⁹ 次循環 | 超時、效率極低 | O(log min(m,n))，極快 (64 位數幾十步) |
5767 % 4453 = 1314 → gcd(4453, 1314)
4453 % 1314 = 511 → gcd(1314, 511)
1314 % 511 = 292 → gcd(511, 292)
511 % 292 = 219 → gcd(292, 219)
292 % 219 = 73 → gcd(219, 73)
219 % 73 = 0 → GCD = 73
LCM = 5767 / 73 * 4453 = 352, ...while (b != 0) 由餘數自然收斂至 0 決定終止，數學保證有限步結束。a=b; b=r; 會不會亂？」b 成為新被除數 a，餘數 r 成為新除數 b，完美對應數學定義。% 是取模還是取商？」% 是**取餘** (模)，a % b 返回餘數，a / b 返回商。219 % 73 = 0 而非 3。求 GCD/LCM **必須掌握輾轉相除法**：代碼極短 (5 行)、時間複雜度對數級、無邊界條件陷阱、通用於任意大小整數。遞減遍歷法僅適合極小數教學演示，實際工程與考試均應使用歐幾里得算法。
