gcd

题目要求将绳子都切成同样的长度，细想可以发现，如果要是该长度能够切出来，那么就一定是切成所有数的公约数。进一步，切成最大公约数，切的次数就是最少的。

所以求出最大公约数，判断每个$a_i$需要切多少次，累计次数并与$k$比较即可。

时间复杂度为$O(TNlogN)$。题目保证$\sum{n}\le1e5$。

代码

题目描述

小红有$n$ 根绳子，从1编号到$n$，每根绳子长度为$a_i$。 小红希望他的绳子们长度相等，他最多切$k$次绳子。

具体的:每次选择一个长度为$s$的绳子，将其切成长度分别为$x,y$的两段

满足:$x,y$均为正整数，且$x+y=s$。 他想知道他是否可以切不超过$k$次绳子，从而满足条件，请你帮帮他吧。

输入描述

本题有多组测试数据，输入包含若干行。 第一行一个正整数 $T(1\le T\le 10^4)$，表示数据组数。

接下来，对于每组测试数据:

第一行两个正整数$n(1 ≤n< 10^5),k(0\le k\le 10^{14})$，分别表示小红拥有

的绳子个数，以及最多的操作次数。

第二行$n$个正整数$a_i(1\le a_i\le 10^9)$，表示每根绳子的长度。

(保证所有测试数据中$n$的总和不超过$10^5$。)

输出描述

输出包含$T$行，对于每个测试数据，如果小红可以做到让绳子一样长输出“YES'否则输出“NO”(不包含双引号)。

样例

输入

2
3 4
1 3 2
4 1
2 2 2 3

输出

YES
NO

说明

第一个测试数据:
将第二根绳子切两刀变为:1,1,1，将第三根绳子切一刀变成1,1。此时所有绳子长度都为1
第二个测试数据：
无方案可以满足条件