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

yu1128_AKIOI · 2024-03-29 21:56:02 · 题解

思路

考虑暴力做法，直接枚举 A_{i,j}，肯定会 TLE。预期得分 30-60 pts。

下面来说正解。

对于每一个 i(1\le i\le N)，可以用数组 a 累计其在 K 以内的所有倍数，同理，对于每一个 i(1\le i\le M) 也是如此。

最后，用 ans 累加 i\times a_i\times b_i(1\le i\le K) 即可。注意 ans 要开 long long。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans;
signed main(){
    cin>>n>>m>>k;
    int a[1000010]={},b[1000010]={};
    for(int i=1;i<=n;i++){
    for(int j=i;j<=k;j+=i){
        a[j]++;
    }
    }
    for(int i=1;i<=n;i++){
    for(int j=i;j<=k;j+=i){
        a[j]++;
    }
    }
    for(int i=1;i<=k;i++) ans+=i*a[i]*b[i];
    cout<<ans;
}