题目描述

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

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

gcd

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

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

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

代码