LeetCode 1250. Check If It Is a Good Array
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^51 <= nums[i] <= 10^9
古代数学的剩余定理，如果2个数互质，a%b==1，那么就存在pa+qb=1，
所以只要数组中所有数字的最大公约数是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.
