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

[GESP202403 八级] 公倍数问题

Description

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

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

方便起见,你只需要输出 k=1Kkansk\sum_{k=1}^{K} k*ans_{k} 即可,其中 anskans_{k} 表示第 kk 名小朋友感兴趣的答案。

Input Format

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

Output Format

输出一行,即 k=1Kkansk\sum_{k=1}^{K} k*ans_{k}

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

2 5 2

9

100 100 100

185233

Hint

样例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,而其余不行。 因此答案是 11+24=91 * 1 + 2 * 4 = 9

数据范围

对于 30%30 \% 的测试点,保证 N,M,K10N, M, K\leq 10

对于 60%60 \% 的测试点,保证 N,M,K500N, M, K\leq 500

对于所有的测试点,保证 N,M105K106N, M \leq 10^{5},K \leq 10^{6} ​。

Source

GESP 2024年03月 C++八级T1