1250. Check If It Is a Good Array

题目信息

题号:

1250

难度:

Hard

主题:

数论、最大公约数、裴蜀定理

原题:

LeetCode 1250

重点:

可以选择数组元素并为其乘任意整数系数;存在整数线性组合等于 1 当且仅当全部元素最大公约数为 1

题目重述

给定正整数数组 nums。若能选择其中若干元素,并为每个被选元素乘上任意整数系数,使所有乘积之和恰好等于 1,则称该数组为好数组。

整数系数可以为正数、零或负数。请判断 nums 是否为好数组。

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

自建示例

整体最大公约数为一时存在整数线性组合:

输入:nums = [6,10,15]
输出:true
解释:三个数的最大公约数为 1,因此根据裴蜀定理可以组合得到 1。

所有元素都有公共因子时无解:

输入:nums = [6,10,14]
输出:false
解释:所有整数线性组合都能被 2 整除,不可能等于 1。