自动搬运

查看原文

来自洛谷，原作者为

	xieziheng 还不是因为我动了资本的蛋糕

搬运于2025-08-24 23:17:59，当前版本为作者最后更新于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，这个数组之后可以重复利用，这样就卡进去了。