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

gcx12012 · 2025-06-14 14:01:51 · 题解

前言

有点不牛的题。

Solution

这里给一个不卡空间的做法，但是跑的会比较慢。

设 n=\prod_{i=1}^k p_i^{c_i}，则 n 的约数个数 d(n)=\prod (c_i+1)。

我们先把 d(n)\le 7 的情况预处理出来，然后开始讨论。

设 p,q,r 为两两不相同的质数。

当 d(n)=8 时，只会有 p^7,pqr,p^3q 这三种情况。

当 d(n)=9 时，只会有 p^2 q^2,p^8 这两种情况。

预处理出来后发现 10^9 内符合条件的数的个数在 2\times 10^7 左右，于是把它们都存下来，然后二分查找即可。