You are given n positive integers as an array. Also, you are given an integer k. Now, try to find a subsequence of the array that (LCM - GCD) of that subsequence equals to k. You don't have to print the subsequence, just print whether it is possible to find a subsequence with given condition or not!
Note: Here, LCM means Least common multiple and GCD means Greatest common divisor. Also subsequence means a new array which can be generated by deleting some values of initial array without changing the order. GCD & LCM of single number are same and equal to the number of itself.
You have to answer T independent queries.First line contains two integers n & k, the length of the array and the value of (LCM - GCD). Second line contains n positive integers as an array a. Let, the value at ith position is ai.
Print "YES", if it is possible to find a subsequence which (LCM - GCD) equals to k. Otherwise, print "NO".Print them without quotes with a newline. And, try to use faster IO as the dataset is huge.
Input | Output |
---|---|
5 5 3 2 4 8 3 6 3 22 6 8 12 3 20 6 8 12 3 6 6 8 12 3 10 6 8 12 | YES YES YES YES NO |
In first case, GCD of {3, 6} is 3 and LCM of same subsequence is 6. So, (LCM - GCD) is 3 here. |