题解：P12174 [蓝桥杯 2025 省 Python B] A · B Problem

CSP_S_2023_T2 · 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）。

显然答案为

也就是

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

所以，我们可以预处理出所有的 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)

（疯狂暗示）