Processing math: 50%

Codeforces1047C 数学

给n个数,问最少删除几个数使得删后序列的gcd大于n个数的gcd
(n3·105,ai107)


题目链接

题解

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

代码