20231203 - Math大合集

因数

• 定义: 若整数 a, b 满足 a / b = c 整除, 则 b 为 a の因数, 同时 c 也为 a の因数

最大公因/约数 (Greatest Common Factor)

• 定义: 两个或多个整数中共有的因数最大那个
• 代码示例:

    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;
    }

• 辗转相除法:

    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)

• 示例:

    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++;
        }
    }