Codeforces1047C 数学 Posted on 2018-09-23 | In ACM , codeforces , 数学 给n个数,问最少删除几个数使得删后序列的gcd大于n个数的gcd(n≤3·105,ai≤107) 题目链接 题解 考虑gcd,因为每个数可以被分解为质因数乘积的形式 删除某些数使得剩下的数有公共因子 故每个数除以n个数gcd,然后考虑每个素数最多出现在n个数中的个数,暴力素数和素数的倍数即可 时间复杂度O((max 代码