题目描述

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个好数组，则返回 True；否则请返回 False。

样例

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

输入：nums = [3,6]
输出：false

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

算法

(数学) $O(n \log M)$

1. 如果选出来的一组数组的最大公约数为 1，则可以满足题中的条件。
2. 证明：如果 $gcd(x_1, x_2, x_3, \dots) = t > 1$，则 $a \cdot x_1 + b \cdot x_2 + c \cdot x_3 + \dots$ 必定是 $t$ 的倍数，所以不可能找到一组系数等于 1。他们的最大公约数一定是 1。

时间复杂度

• 每个数字遍历一次，然后求最大公约数，时间复杂度为 $O(n \log M)$。

空间复杂度

• 仅需要 $O(\log M)$ 的空间求最大公约数，可以改为迭代消除这一部分的空间。

C++ 代码

class Solution {
public:
    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    bool isGoodArray(vector<int>& nums) {
        int n = nums.size();

        int x = nums[0];
        for (int i = 1; i < n; i++)
            x = gcd(x, nums[i]);

        return x == 1;
    }
};