[GESP202403八级]公倍数

阅读量: 198 编辑

26、公倍数问题

小 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 。

1 ≤ N,M,K ≤ 1e5

【输出描述】

输出一行,即运算结果。

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

【输入样例】

2 5 2

【输出样例】

9

【参考程序】

// 爱码岛编程 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;
}
爱码岛编程公众号
试卷资料
爱码岛编程小程序
在线刷题
苏ICP备13052010号
©2023 南京匠成信息科技有限公司