Matrix LCM Occurrences

Little A wrote an $N\times M$ matrix $A$, but we cannot see this matrix. We only know that the element in the $i$-th row and $j$-th column, $A_{i,j}$, is a common multiple of $i$ and $j$ (for $i=1,\dots,N$, $j=1,\dots,M$). There are $K$ children. The $k$-th child wants to know the maximum number of elements in $A$ that can be equal to $k$ (for $k=1,2,\dots,K$). Note that each child's answer is independent; that is, if some cell can possibly be assigned two different values, it counts for both children.

For a cell $(i,j)$ to be equal to $k$, it is necessary and sufficient that $k$ is a common multiple of both $i$ and $j$, i.e. if and only if $$i\mid k \quad \text{and} \quad j\mid k.$$

Thus, the maximum possible number of cells that can be assigned the value $k$, denoted by $ans_k$, is given by $$ans_k=\#\{(i,j)\;|\;1\le i\le N,\; 1\le j\le M,\; i\mid k \text{ and } j\mid k\}.$$

Since you only need to output the sum $$\sum_{k=1}^{K} k\times ans_k,$$ we can reverse the order of summation. Observe that an element at position $(i,j)$ can take the value $k$ if and only if $k$ is a multiple of the least common multiple (LCM) of $i$ and $j$. Let $$L=\mathrm{lcm}(i,j).$$ Then $k$ can be equal to $A_{i,j}$ if $L\mid k$. For each cell $(i,j)$, let $$q=\left\lfloor\frac{K}{L}\right\rfloor.$$ The sum of all multiples of $L$ up to $K$ is $$L\times\frac{q(q+1)}{2}.$$

Therefore, the required answer is $$\sum_{i=1}^{N}\sum_{j=1}^{M}\left(L\times\frac{q(q+1)}{2}\right),$$ where $q=\left\lfloor\frac{K}{\mathrm{lcm}(i,j)}\right\rfloor$.

inputFormat

The input consists of a single line containing three integers $N$, $M$, and $K$.

outputFormat

Output a single integer: $$\sum_{k=1}^{K} k\times ans_k.$$

sample

2 2 10

145