20231203 - Math大合集
因数
- 定义: 若整数 a, b 满足 a / b = c 整除, 则 b 为 a の因数, 同时 c 也为 a の因数
最大公因/约数 (Greatest Common Factor)
- 定义: 两个或多个整数中共有的因数最大那个
- 代码示例:cpp
int GCF(int n, int m) { for (int i=min(n, m); i > 0; i --) { if (m % i + n % i == 0) { return i; } } return 0; }
- 辗转相除法:cpp
int GCF(int n, int m) { int r; // n > m ? swap(n, m) : NULL; // 这样子可以少一次循环 (期待 m > n) while(m % n) { r = m % n; m = n; n = r; } return n; }
最小公倍数 (Least Common Multiple)
- 示例:cpp
int LCM(int m, int n) { // 有可能卡在 while(x int min_num = min(m, n); int max_num = max(m, n); if (max_num % min_num == 0) { return max_num; } int i = min_num + 1; while (true) { if (i % m + i % n == 0) { return i; } i++; } }