题解：P10263 [GESP202403 八级]公倍数问题

· · 题解

题目分析

题目中在不断的强调二维数组，也是挖了一个大大的坑！给出的数据范围中，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;
}