1250. Check If It Is a Good Array¶
题目信息¶
- 题号:
1250
- 难度:
Hard
- 主题:
数论、最大公约数、裴蜀定理
- 原题:
- 重点:
可以选择数组元素并为其乘任意整数系数;存在整数线性组合等于
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。