Given an array?nums?of?positive integers.?

Your task is to select some subset of?nums,

multiply each element by an integer and add all these numbers.

?The array is said to be?good?if you can obtain a sum of?1?from the array by any possible subset and multiplicand.

Return?True?if the array is?good?otherwise?return?False.

?

Example 1:

Input: nums = [12,5,7,23]

Output: true

Explanation:?

Pick numbers 5 and 7. 5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]

Output: true

Explanation:?

Pick numbers 29, 6 and 10. 29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]

Output: false

?

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

古代數(shù)學的剩余定理，如果2個數(shù)互質，a%b==1，那么就存在pa+qb=1，

所以只要數(shù)組中所有數(shù)字的最大公約數(shù)是1，那么他們就能組成1，否則不能；

Runtime:?3 ms, faster than?62.25%?of?Java?online submissions for?Check If It Is a Good Array.

Memory Usage:?52.6 MB, less than?29.80%?of?Java?online submissions for?Check If It Is a Good Array.