gcd 函數
[編輯] [转简体] (简体译文)
|
作者:huidong
| 分類:【算法】雜項
[
3 瀏覽
0 評論
0 贊
0 踩
]
概要
求解最大公因數
正文
輾轉相除法
int gcd(int m, int n) { if (!m || !n) return 1; // 準備輾轉相除,首先使 a >= b,r 記錄餘數 int a = m, b = n, r = 0; if (a < b) a ^= b ^= a ^= b; do { r = a % b; a = b; b = r; } while (r != 0); return a; }
m * n == 0 時返回 1。