主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF912E Prime Gift
最后更新于 2025-08-28 08:41:47
作者
2huk
分类
题解
题解
CF912E
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
meet-in-the-middle。 考虑将 $n$ 个质数分成前 $\lfloor n/2\rfloor$ 个和后 $n-\lfloor n/2\rfloor$ 个。也就是说这两组的大小都 $\le 8$。分别暴力（dfs）枚举一组内的数能得到的数（即，哪些数的质因子只包括前 $\lfloor n/2\rfloor$ 个质数）。 可以发现这样得到的两个数组的大小很小。验证发现当一组是 $2,3,5,7,11,13,17,19$ 时这个数组的长度最大，为 $7039193$。当然实际上远小于这个数，但无所谓。 于是变成了，给定了两个数组 $a,b$，求 $a_i \times b_j$ 的第 $k$ 大。这是经典问题。二分答案并双指针扫描两个数组即可。 然后我为了卡一点时间把输入的数组 `random_shuffle` 了一下。
正在渲染内容...
点赞
2
收藏
0
