第2题-小红割绳子

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

gcd

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

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

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

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

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