2020年广东工业大学第十届文远知行杯新生程序设计竞赛（同步赛） E-枚举求和

E-枚举求和

原题传送门

题目描述

这道题是一个很简单的枚举题：给定n,m,k求:

符号意义均为数学表达中的一般意义。
符号解释：为防止读不懂符号意义，做符号解释:
gcd(i,j)表示i与j的最大公因数。
表示的是k为gcd(i,j)的因子；
[ ]表示当[ ]内的命题为真，则结果为1，若为假，则为0； 例如[这道题是一个很简单的枚举题]等于1
输入描述
第一行输入一个t(1<=t<=100000);表示有t组输入数据
接下来的t行，每行输入n ，m，k；(1<=n,m,k<=1000000)
输出描述
对于每一行输入数据，输出一个数表示求和后的答案；
示例1
输入
2
2 2 1
2 3 2
输出
4
1

解析

根据这道题的数据量来看，如果想模拟题目所描述的过程枚举的话，是会TLE的 我还真信题目了！！
首先，咱们要弄明白什么是一个数的因子

随便举一个数：14。其中，能把14整除的整数有1、2、7、14。除了14（它本身）以外，剩下四个能把14整除的数字1、2、4、7可以被称作14的因子（因数）。

也就是说，咱们需要找到gcd(i, j)能被k整除( gcd(i, j) 是k的倍数 )*的情况有多少种，即 gcd(i, j) % k == 0有多少种情况
什么时候gcd(i, j)的结果能被k整除呢？ 思考之后，你会发现，当 i 和 j 都是k的倍数时，那么gcd(i, j)的结果一定会被k整除
这个时候再回到题目，咱们只需要找一下 m 和 n 中，有多少个k的倍数，即m / k和n / k的数量，二者相乘之后，得到了我们最终的答案是(m / k) * (n / k)

注意一下数据范围！！！

AC代码

#include<iostream>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        long long m, n, k, ans; //考虑到数据范围，选择无脑long long
        cin >> m >> n >> k;
        ans = (m / k) * (n / k);
        cout << ans << endl;
    }
    return 0;
}

如果觉得哪里叙述的不妥，欢迎给位大佬指出