自动搬运

查看原文

来自洛谷，原作者为

	CSP_S_2023_T2 时代的灰尘落在个人头上，就是一座山，但总有人愿意成为移山的愚公

搬运于2025-08-24 23:13:24，当前版本为作者最后更新于2025-04-13 19:43:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

Step 1：

对于 $1$ 到 $L$ 之间的每一个满足条件的整数 $i$：

先枚举所有可能的 $X_A \cdot X_B$ 以及 $Y_A \cdot Y_B$，再枚举所有可能的 $X_A,X_B,Y_A,Y_B$。

时间复杂度 $O(L^2 \sqrt L)$，会超时。

Step 2：

我们定义 $f(x)$ 为 $x$ 能表示为不同的两个正整数的乘积的种类数（即 $x$ 的因数个数）。

如 $f(6)=4$（$6=1\times6=2\times3=3\times2=6\times1$）。

显然答案为

$$\sum_{i=1}^{L-1} \sum_{j=1}^{L-i} f(i) \times f(j) $$

也就是

$$\sum_{i=1}^{L-1} \big( f(i) \times \sum_{j=1}^{L-i} f(j) \big) $$

不懂的可以自己手推一下。

所以，我们可以预处理出所有的 $f(x)$，再用一次前缀和，时间复杂度就来到了 $O(L \sqrt L)$。

此时 C++ 已经能过了，但是 Python 还不能。

Step 3：

考虑对预处理进行优化。

我们发现，在预处理的过程中，寻找 $x$ 的因数需要枚举 $\sqrt x$ 次，远大于 $x$ 的因数个数。

所以，我们不妨枚举所有因数，即先从 $1$ 到 $L$ 枚举所有整数 $i$，然后枚举 $i$ 的所有倍数，将计数数组的这一项 $+1$ 即可。

容易发现时间复杂度即为调和级数（不懂的自己百度），也就是 $O(L \log L)$。

此时 Python 也能过了。

于是这道题就做完了。

代码

n=int(input())
ans=0
a=[0]*1048577     #1048577=2^20+1
b=[0]*1048577
for i in range(1,n+1):
    for j in range(i,n+1,i):
        a[j]=a[j]+1          #计数器 +1
for i in range(1,n+1):
    b[i]=b[i-1]+a[i]         #前缀和数组
for i in range(1,n+1):
    ans=ans+a[i]*b[n-i]      #统计答案
print(ans)

（疯狂暗示）