本文涉及知识点

菲蜀定理 子序列

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;
    }
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。