专栏文章

题解：P12766 [POI 2018 R3] 完备数 Complete numbers

ggcx12012
P12766题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip3epcn
此快照首次捕获于
2025/12/03 05:31
3 个月前
此快照最后确认于
2025/12/03 05:31
3 个月前
查看原文

前言

有点不牛的题。

Solution

这里给一个不卡空间的做法，但是跑的会比较慢。
设 n=∏i=1kpicin=\prod_{i=1}^k p_i^{c_i}，则 nn 的约数个数 d(n)=∏(ci+1)d(n)=\prod (c_i+1)。
我们先把 d(n)≤7d(n)\le 7 的情况预处理出来，然后开始讨论。
设 p,q,rp,q,r 为两两不相同的质数。
当 d(n)=8d(n)=8 时，只会有 p7,pqr,p3qp^7,pqr,p^3q 这三种情况。
当 d(n)=9d(n)=9 时，只会有 p2q2,p8p^2 q^2,p^8 这两种情况。
预处理出来后发现 10910^9 内符合条件的数的个数在 2×1072\times 10^7 左右，于是把它们都存下来，然后二分查找即可。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...