Leetcode.1250 检查「好数组」

题目链接

Leetcode.1250 检查「好数组」 Rating ： 1983

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

分析：

解决本题需要学习下 裴蜀定理(Bézout’s identity)。

多个整数之间的裴蜀定理

设 $a_1....a_n$ 共 $n$ 个整数，$d$ 是这个$n$个数的最大公约数，那么就肯定存在 $x_1....x_n$ 使得 $a_1\ast x_1...a_n\ast x_n=d$。

特殊的情况是，只要当 $a_1...a_n$ 中有存在两个或以上的数互质，那么就一定存在 $x_1,x_2...x_n$ 使得 $a_1\ast x_1+a_2\ast x_2...a_n\ast x_n=1$。

时间复杂度：$O(nlogm)$

代码：

class Solution {
public:
    //求 a 和 b 的最大公约数
    int gcd(int a,int b){
        return b ? gcd(b,a%b) : a;
    }
    bool isGoodArray(vector<int>& nums) {
        int g = 0;
        for(auto x:nums){
            g = gcd(g,x);
            //g == 1 说明 nums 中一定存在两个数以上的互质
            if(g == 1) break;
        }

        return g == 1;
    }
};