【菲蜀定理 子序列】1250 检查「好数组」

本文涉及知识点

菲蜀定理 子序列

LeetCode 1250 检查「好数组」

给你一个正整数数组 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⁵

1 <= nums[i] <= 10⁹

菲蜀定理

根据菲蜀定理，任意子序列互质就可以。任意子序列互质，则整个数组必定互质。

判断整个数组是否互质。

VS 和 GCC都有gcd函数。

代码

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
int iGCD = nums[0];
for(int i = 1 ; i < nums.size();i++){
    iGCD = gcd(iGCD,nums[i]);
}
return 1 == iGCD;
    }
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。