算法-E10C-最大公约数

今天碰到一道有意思的题目，学到了很多东西，所以记录一下

检查好数组

碰到之后完全不知道如何入手，最后通过看解答才弄明白，但是中间有很多知识点可以记录一下

首先 需要知道裴蜀定理，又称贝祖定理，是一个最大公约数定理：设 a, b 是不全为零的整数，则存在整数 x , y , 使得

$$ax + by = gcd(a, b)$$

1. 若任何一个等于0，则 $gcd(a, b) == a$

2. 对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程

   $$ax + by = m$$

   有解当前仅当 m 是 d 的倍数

这里有一个奇特的点 0 因为没有因数，所以 0 不与其他数存在最大公约数，等我看了 类欧几里德算法 再补充

所以 $ax + by = 1$ 有解，那么 $gcd(a, b) = 1$

其次 我们如何求一个两个数的最大公约数，经典的 辗转相除法(又称 欧几里德算法)

//也可以使用现有函数 gcd(a, b)
int GCD(int a, int b) {
	return b ? GCD(b, a % b) : a;
}

证明 $gcd(a, b) = gcd(b, a \% b)$ 过程如下

1. 设 $a = bk + c$，所以 $c = a \% b$

2. 设 d 是 a , b 的公约数

3. 所以 $a / d = b / d * k + c / d$

4. 因为 $a / d$ 与 $b / d * k$ 是整数，所以 $c / d$ 也是整数

5. 将 $c = a \% b$ 带入第3步得 $a / d - b / d * k = a \% b / d$，因为 左边是整数，所有等式右边也是整数

6. 那么 $a / d = a \% b / d + b / d * k$，那么 d 也是 b, $a \% b$ 的约数，也是 a, b 的约数

7. 尽然两式的公约数是相同的，那么最大公约数也会相同

8. 所以 $gcd(a, b) = gcd(b, a mod b)$

最后就是这个题目的解答

class Solution {
public:
    int Gcd(int a, int b) {
        return b ? Gcd(b, a % b) : a;
    }
    bool isGoodArray(vector<int>& nums) {
        int v = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            if(v == 1) return true;	//1与任意正整数的最大公约数是1
            v = Gcd(nums[i], v);
        }
        return v == 1;
    }
};

参考链接

1. https://oi-wiki.org/math/number-theory/gcd/
2. https://leetcode.cn/problems/check-if-it-is-a-good-array/
3. https://oi-wiki.org/math/number-theory/bezouts/