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

xieziheng · 2025-06-12 18:11:59 · 题解

我的评价为，卡空间题。

首先把答案差分是显然的。然后发现 a,b\leq 10^9，然后你其实可以预处理掉 a,b<10^8 的情况以规避掉很多讨论。记 \sigma(x) 为 x 约数个数，考虑 x\in[10^8,10^9)\cap \mathbb N,\sigma(x)=9 则 x 形如 p^8 或 p^2q^2，p,q 为质数。前一种情况只有 p=11,13 后一种情况有 pq\leq \sqrt {10^9} 也是容易预处理的，于是就做完了。

但是你发现还需要卡空间，欧拉筛你需要的约数数组和最小质因子次幂数组其实可以合并成一个 int，这个数组之后可以重复利用，这样就卡进去了。