题目要求将绳子都切成同样的长度,细想可以发现,如果要是该长度能够切出来,那么就一定是切成所有数的公约数。进一步,切成最大公约数,切的次数就是最少的。
所以求出最大公约数,判断每个ai需要切多少次,累计次数并与k比较即可。
时间复杂度为O(TNlogN)。题目保证∑n≤1e5。
小红有n 根绳子,从1编号到n,每根绳子长度为ai。 小红希望他的绳子们长度相等,他最多切k次绳子。
具体的:每次选择一个长度为s的绳子,将其切成长度分别为x,y的两段
满足:x,y均为正整数,且x+y=s。 他想知道他是否可以切不超过k次绳子,从而满足条件,请你帮帮他吧。
本题有多组测试数据,输入包含若干行。 第一行一个正整数 T(1≤T≤104),表示数据组数。
接下来,对于每组测试数据:
第一行两个正整数n(1≤n<105),k(0≤k≤1014),分别表示小红拥有
的绳子个数,以及最多的操作次数。
第二行n个正整数ai(1≤ai≤109),表示每根绳子的长度。
(保证所有测试数据中n的总和不超过105。)
输出包含T行,对于每个测试数据,如果小红可以做到让绳子一样长输出“YES'否则输出“NO”(不包含双引号)。
输入
2
3 4
1 3 2
4 1
2 2 2 3
输出
YES
NO
说明
第一个测试数据:
将第二根绳子切两刀变为:1,1,1,将第三根绳子切一刀变成1,1。此时所有绳子长度都为1
第二个测试数据:
无方案可以满足条件