襄阳网站建设xytzg,wordpress get_comments,做购物平台网站需要注意什么,天网网站建设题目链接 Leetcode.1250 检查「好数组」 Rating #xff1a; 1983 题目描述
给你一个正整数数组 nums#xff0c;你需要从中任选一些子集#xff0c;然后将子集中每一个数乘以一个 任意整数#xff0c;并求出他们的和。
假如该和结果为 1#xff0c;那么原数组就是一个「…题目链接 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 提示
1nums.length1051 nums.length 10^51nums.length1051nums[i]1091 nums[i] 10^91nums[i]109
分析
解决本题需要学习下 裴蜀定理(Bézout’s identity)。
多个整数之间的裴蜀定理
设 a1....ana_1....a_na1....an 共 nnn 个整数ddd 是这个nnn个数的最大公约数那么就肯定存在 x1....xnx_1....x_nx1....xn 使得 a1∗x1...an∗xnda_1 * x_1...a_n * x_n da1∗x1...an∗xnd。
特殊的情况是只要当 a1...ana_1...a_na1...an 中有存在两个或以上的数互质那么就一定存在 x1,x2...xnx_1,x_2...x_nx1,x2...xn 使得 a1∗x1a2∗x2...an∗xn1a_1 * x_1 a_2 * x_2...a_n * x_n 1a1∗x1a2∗x2...an∗xn1。
时间复杂度O(nlogm)O(nlogm)O(nlogm)
代码
class Solution {
public://求 a 和 b 的最大公约数int gcd(int a,int b){return b ? gcd(b,a%b) : a;}bool isGoodArray(vectorint nums) {int g 0;for(auto x:nums){g gcd(g,x);//g 1 说明 nums 中一定存在两个数以上的互质if(g 1) break;}return g 1;}
};
