GESP认证C++编程真题解析 | P10263 [GESP202403 八级] 公倍数问题

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[P10263 GESP202403 八级] 公倍数问题 - 洛谷

【题目描述】

小 A 写了一个N × M N \times MN×M的矩阵A AA，我们看不到这个矩阵，但我们可以知道，其中第i ii行第j jj列的元素A i , j A_{i,j}Ai,j​是i ii和j jj的公倍数（i = 1 , … , N i=1,\dots,Ni=1,…,N，j = 1 , … , M j=1,\dots,Mj=1,…,M）。现在有K KK个小朋友，其中第k kk个小朋友想知道，矩阵A AA中最多有多少个元素可以是k kk（k = 1 , 2 , … , K k=1,2,\dots,Kk=1,2,…,K）。请你帮助这些小朋友求解。

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

方便起见，你只需要输出∑ k = 1 K k × ans k \sum_{k=1}^{K}{k \times \texttt{ans}_k}∑k=1K​k×ansk​即可，其中ans k \texttt{ans}_kansk​表示第k kk名小朋友感兴趣的答案。

【输入】

第一行三个正整数N , M , K N,M,KN,M,K。

【输出】

输出一行，即∑ k = 1 K k × ans k \sum_{k=1}^{K}{k \times \texttt{ans}_k}∑k=1K​k×ansk​。

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

【输入样例】

2 5 2

【输出样例】

9

【算法标签】

《洛谷 P10263 公倍数问题》 #数学# #调和级数# #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义int为long long类型intn,m,k,ans;// n: 行数, m: 列数, k: 遍历范围, ans: 答案inta[1000005],b[1000005];// a: 存储1~1000000的因数个数（针对n）, b: 存储1~1000000的因数个数（针对m）// 预处理函数：计算1~1000000的因数个数// divisor[]: 存储结果的数组// n: 实际需要计算的最大值voidcount_divisor(intn,intdivisor[]){// 类似埃氏筛法计算每个数的因数个数for(inti=1;i<=n;i++)// i是可能的因数{// 将i的倍数都增加1，因为i是这些数的因数for(intj=i;j<=1000000;j+=i){divisor[j]+=1;// j的因数个数加1}}}signedmain()// 因为#define int long long，所以用signed main{// 输入n, m, kcin>>n>>m>>k;// 预处理计算因数个数// a[i]: 表示在1~n范围内，i的因数个数// b[i]: 表示在1~m范围内，i的因数个数count_divisor(n,a);count_divisor(m,b);// 计算答案for(inti=1;i<=k;i++)// 遍历1到k{// 计算公式：ans = Σ(i=1 to k) [i * a[i] * b[i]]ans+=i*a[i]*b[i];// 调试输出// cout << "ans " << ans << endl;}// 输出结果cout<<ans<<endl;return0;}

【运行结果】

2 5 2 9