试题名称:公倍数问题
3.1.1 问题描述
小A写了一个 的矩阵 ,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Ai,j是i和j的公倍数( i=1,.....,N,j=1, ,.....,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,.....,K )。请你帮助这些小朋友求解。
注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。
方便起见,你只需要输出即可,其中ansk表示第k名小朋友感兴趣的答案。
3.1.2 输入描述
第一行三个正整数N,M,K。
3.1.3 输出描述
输出一行,即。
请注意,这个数可能很大,使用C++语言的选手请酌情使用long long等数据类型存储答案。
3.1.4 特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
3.1.5 样例输入1
3.1.6 样例输出1
3.1.7 样例解释1
只有A1,1可以是1,其余都不行。
A1,1A1,2A2,1A2,2都可以是2,而其余不行。
因此答案是1×1+2×4=9。
3.1.8 样例输入2
3.1.9 样例输出2
3.1.10 数据规模
对于30的测试点,保证N,M,K≤10;
对于60的测试点,保证N,M,K≤500;
对于100的测试点,保证N,M≤105,K≤106。