[GESP202403 八级] 公倍数

C++编程GESP真题试卷

[GESP202403 八级] 公倍数

阅读量: 84 编辑

小 A 写了一个 N×M 的矩阵，我们看不到这个矩阵，但我们可以知道，其中第 i 行第 j 列的元素 Aᵢⱼ 是 i 和 j 的公倍数（i=1，...，N，j=1，...，M）。现在有K个小朋友，其中第k个小朋友想知道，矩阵A 中最多有多少个元素可以是k（k=1，2，...，K）。请你帮助这些小朋友求解。

注意：每位小朋友的答案互不相关，例如，有些位置既可能是 x，又可能是y ，则它同可以时满足x，y两名小朋友的要求。

方便起见，你只需要输出求和即可，其中ansₖ表示第 k 名小朋友感兴趣的答案。

【输入描述】

第一行三个正整数N，M，K 。N，M，K ≤ 1e5

【输出描述】

输出一行，即运算结果。

请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。

【输入样例】

2 5 2

【输出样例】

【参考程序】

// 爱码岛编程 P10263
#include <bits/stdc++.h>
using namespace std;

int N, M, K;
vector<int> Si, Sj;

int main() {
    cin >> N >> M >> K;
    
    Si.resize(K + 5, 0);
    Sj.resize(K + 5, 0);
    
    for (int i = 1; i <= N; i++) {
        // t+=i保证了t和i是约数
        for (int t = i; t <= K; t += i) {
            Si[t] += 1;
        }
    }

    for (int j = 1; j <= M; j++) {
        // t+=j保证了t和j是约数
        for (int t = j; t <= K; t += j) {
            Sj[t] += 1;
        }
    }

    long long result = 0;
    for (int k = 1; k <= K; ++k) {
        result += (long long)k * Si[k] * Sj[k];
    }
    cout << result << endl;

    return 0;
}