自动搬运

查看原文

来自洛谷，原作者为

	superballll **

搬运于2025-08-24 22:56:19，当前版本为作者最后更新于2024-03-26 01:04:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

题目中在不断的强调二维数组，也是挖了一个大大的坑！给出的数据范围中，$1\leq N,M\le10^5$ 这个二维数组一旦开了，就会喜提 MLE，直接就是 $0$ 分，小数据范围的 $60$ 分都是拿不到的。

其实题目中注意部分也进行了提示，就是二维数组中的值为了满足小朋友的要求是可以进行改变了的，而且是不是公倍数只跟二维数组 $A$ 的两个下标 $i$ 和 $j$ 有关，即只要能成为 $i$ 和 $j$ 的公倍数就符合要求。

假设 $k$ 是 $i$ 和 $j$ 的公倍数，那也就意味着 $i$ 和 $j$ 都是 $k$ 的因数，我们结合输入输出样例来进行分析：

当 $k=1$ 时，只有 $A_{1,1}$ 符合要求，这是因为 $1$ 只能是 $1$ 和 $1$ 的公倍数，也就是说因为 $1$ 的因数只有 $1$，因此是 $1\times1=1$ 个。

当 $k=2$ 时，$2$ 的因数有 $1$ 和 $2$，因此 $A_{1,1}$ $A_{1,2}$ $A_{2,1}$ $A_{2,2}$ 共 $2\times2=4$ 个位置都符合要求。

当 $k=4$ 时，$4$ 有 $1$ $2$ $4$ 共 $3$ 个因数，那么就有 $3\times3=9$ 个位置符合要求，如下图所示：

当然，我们还要注意 $N$ 和 $M$ 的值，如果因数超出了相应的范围，我们就不能计算在内了。因此，这道题就变成：找到 $k$ 在分别在 $1 \sim N$ 和 $1 \sim M$ 范围内的因数的个数 $sn$ 和 $sm$，此时 $sn\times sm$ 即为 $k$ 符合要求的位置个数。最后分别求出 $1 \sim K$ 的符合要求的个数再按要求乘上系数再累加求和即可。

复杂度分析

如果采用枚举法分别枚举 $1 \sim K$ 在 $1 \sim N$ 和 $1 \sim M$ 中的因子个数的话，时间复杂度肯定会超，那我们换一种思路来实现该部分的操作。

对于数组字 $1$，是所有的 $k$ 的因子；
对于数组字 $2$，是 $2,2+2\times1,2+2\times2,...$等数字的因子；
对于数组字 $3$，是 $3,3+3\times1,3+3\times2,...$等数字的因子。
因此，可用如下程序实现上述操作：

for(int i=1;i<=N;i++)
	for(int j=i;j<=K;j=j+i)
		sn[j]++;

此时 $sn[k]$ 表示在题目中二维数组的行中，$k$ 的因数的个数。然后用同样的方法求出在二维数组的列中 $sm[1] \sim sm[K]$ 的值，并在最终的计算中将两个数组的值以及系数 $k$ 相乘然后累加求和即可得到最终的结果。另外，别忘了开 long long，以及在计算最后的答案时，小心由于循环中定义的局部变量类型为 int 而导致的最终结果的错误！

代码

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
int sn[1000005],sm[1000005];
long long ans=0;

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=k;j=j+i)
			sn[j]++;
	for(int i=1;i<=m;i++)
		for(int j=i;j<=k;j=j+i)
			sm[j]++;
	for(int i=1;i<=k;i++)
		ans+=(long long)i*sn[i]*sm[i];
		
	cout<<ans;
	return 0;
}