#G1042. [GESP202403 八级] 公倍数问题

[GESP202403 八级] 公倍数问题

[GESP202403 八级] 公倍数问题

题目描述

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

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

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

输入格式

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

输出格式

输出一行,即 ∑k=1Kk×ansk\sum_{k=1}^{K} k \times \text{ans}_k。

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

样例 #1

样例输入 #1

2 5 2

样例输出 #1

9

样例解释 #1

只有 A1,1A_{1,1} 可以是 1,其余都不行。

A1,1,A1,2,A2,1,A2,2A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2} 都可以是 2,而其余不行。

因此答案是 1×1+2×4=91 \times 1 + 2 \times 4 = 9。

样例 #2

样例输入 #2

100 100 100

样例输出 #2

185233

数据范围

测试点 数据范围 说明
1~3 N,M,K≤10N, M, K ≤ 10 占 30%
4~6 N,M,K≤500N, M, K ≤ 500 占 60%
全部 N,M≤105N, M ≤ 10^5,K≤106K ≤ 10^6 全部数据