简答题
偏难
#21455
公倍数问题 问题描述 小 A 写了一个N×M的矩阵A,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Aij是i和j的公倍数(i=1,...,N,j=…
公倍数问题
问题描述
小 A 写了一个N×M的矩阵A,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Aij是i和j的公倍数(i=1,...,N,j=1,...,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,...,K)。请你帮助这些小朋友求解。
注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。
方便起见,你只需要输出
即可,其中ansk表示第k名小朋友感兴趣的答案。
输入描述
第一行三个正整数N,M,K。
输出描述
输出一行,即
。
请注意,这个数可能很大,使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
只有A1,1可以是1,其余都不行。
A1,1,A1,2,A2,1,A2,2都可以是2,而其余不行。
因此答案是1×1+2×4=9。
样例输入 2
样例输出 2
数据规模
对于30的测试点,保证N,M,K≤10;
对于60的测试点,保证N,M,K≤500;
对于100的测试点,保证N,M≤105,K≤106。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
using namespace std;
vector<int> count_divisors(int limit, int num) {
vector<int> s(num + 1, 0);
for (int i = 1; i <= limit; ++i) {
for (int j = i; j <= num; j += i) {
s[j] += 1;
}
}
return s;
}
int main() {
int N, M, K;
cin >> N >> M >> K;
vector<int> s_N = count_divisors(N, 1000000);
vector<int> s_M = count_divisors(M, 1000000);
long long result = 0;
for (int k = 1; k <= K; ++k) {
result += (long long)k * s_N[k] * s_M[k];
}
cout << result << endl;
return 0;
}</pre>
这道题暂未补解析。