信息
- ID
- 5485
- 时间
- 4000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
考虑令一个数一定选择,那么我们枚举它的因数,对每个是因数倍数的数进行统计,判断是否存在一个数量 ≥2n 即可。
时间复杂度:找出所有因数 Θ(n),排序 Θ(nlogn),统计 Θ(n+d2(n)),总时间复杂度 Θ(nlogn+d2(n))。
那么随机选取 x 个数如上计算,由于每个数不被选中的概率是 21,故这样的随机化算法有 2x1 的概率出错。那么 x 取到 12 左右即可 AC。
由于这里 n 最大到 106,直接使用 rand()
容易挂,改为 ((long long)rand()<<31)|rand()
较为保险。