P10263 [GESP202403 Level 8] Common Multiple Problem

Related multiple-choice and true/false questions: .

Xiao A wrote an $N \times M$ matrix $A$. We cannot see this matrix, but we know that the element $A_{i,j}$ in row $i$ and column $j$ is a common multiple of $i$ and $j$ ($i=1,\dots,N$, $j=1,\dots,M$). Now there are $K$ children. The $k$-th child wants to know: in matrix $A$, what is the maximum number of elements that can be equal to $k$ ($k=1,2,\dots,K$). Please help them compute the answers. Note: the answers for different children are independent. For example, if some positions can be $x$ and also can be $y$, then those positions can satisfy both children $x$ and $y at the same time. For convenience, you only need to output $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$, where $\texttt{ans}_k$ denotes the answer that the $k$-th child is interested in.

The first line contains three positive integers $N, M, K$.

Output one line: $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$. Please note that this number may be very large. If you are using C++, consider using data types such as `long long` to store the answer.

### Sample 1 Explanation Only $A_{1,1}$ can be $1$; all the others cannot. $A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2}$ can all be $2$, and the others cannot. So the answer is $1 \times 1 + 2 \times 4 = 9$. ### Constraints For $30\%$ of the testdata, $N, M, K \leq 10$. For $60\%$ of the testdata, $N, M, K \leq 500$. For $100\%$ of the testdata, $N, M \leq 10^5$, and $K \leq 10^6$. Translated by ChatGPT 5