GCD

虽然不是lc原题, 但却非常重要. 比如用于斜率比较. 辗转相除法. 代码如下:

  public int GCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);
    }

为什么辗转相除法是对? 已知a = bq + r, 求(a, b) = (b, r = a % b) 若d1 为a, b公因数, 那么r同样也是d1的倍数, 比如a是6倍, b是两倍, bq是四倍, 那么剩下的r就是两倍了. 同理若d2 为b, r的公因数, 那么a也是d2的倍数.