Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1148.

Problem Description

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.

Input Format

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

Output Format

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.

2 5 2

9

100 100 100

185233

Hint

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