G8003 [GESP202403 八级] 公倍数问题 题解

知识点：数论、因数计数、筛法。

解题思路

交换求和顺序，对每个i≤k计算[1,n]内i的因数数量a[i]与[1,m]内i的因数数量b[i]，累加i*a[i]*b[i]，因数计数用枚举倍数筛。

为什么正确

i是某对数的公倍数，当且仅当两数都是i的因数，所以它在总和中出现a[i]b[i]次。

易错点

不是仅计算最小公倍数，也不是只统计方案数；每次贡献还需乘共同倍数i。

复杂度

时间O(k log k)，空间O(k)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>a(k+1),b(k+1);
    for(int i=1;i<=min(n,k);i++)for(int j=i;j<=k;j+=i)a[j]++;
    for(int i=1;i<=min(m,k);i++)for(int j=i;j<=k;j+=i)b[j]++;
    long long ans=0;
    for(int i=1;i<=k;i++)ans+=1LL*i*a[i]*b[i];
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。