Codeforces1047C 数学

给n个数，问最少删除几个数使得删后序列的gcd大于n个数的gcd
$(n\le 3·10^5,a_i\le 10^7)$

---

题目链接

题解

• 考虑gcd，因为每个数可以被分解为质因数乘积的形式
• 删除某些数使得剩下的数有公共因子
• 故每个数除以n个数gcd，然后考虑每个素数最多出现在n个数中的个数，暴力素数和素数的倍数即可
• 时间复杂度$O((\max a_i) \log (\max a_i))$

代码