P1829 [CTT] Crash's Number Table / JZPTAB

In today's math class, Crash learned about the Least Common Multiple. For two positive integers $a$ and $b$, $\text{lcm}(a, b)$ denotes the smallest positive integer divisible by both $a$ and $b$. For example, $\text{lcm}(6, 8) = 24$. After returning home, Crash was still thinking about what he learned. To study the Least Common Multiple, he drew an $n \times m$ table. Each cell contains a number, where the cell in the $i$-th row and $j$-th column contains $\text{lcm}(i, j)$. Looking at this table, Crash thought of many questions. The one he most wants to solve is very simple: what is the sum of all the numbers in this table? When $n$ and $m$ are large, Crash cannot handle it, so he asks you to write a program to compute the answer. Since the result can be very large, Crash only wants the sum modulo $20101009$.

The input contains one line with two integers $n$ and $m$.

Output one positive integer, the sum of all numbers in the table modulo $20101009$.

Sample 1 Explanation: The table is: | $1$ | $2$ | $3$ | $4$ | $5$ | |:-:|:-:|:-:|:-:|:-:| | $2$ | $2$ | $6$ | $4$ | $10$ | | $3$ | $6$ | $3$ | $12$ | $15$ | | $4$ | $4$ | $12$ | $4$ | $20$ | Constraints: - For $30\%$ of the testdata, $n, m \le 10^3$. - For $70\%$ of the testdata, $n, m \le 10^5$. - For $100\%$ of the testdata, $1 \le n, m \le 10^7$. Translated by ChatGPT 5