P4562 [JXOI2018] Game

Jiutiao Kelian (pinyin) is a wealthy girl.

After growing up, she started a business and founded a company. However, managing a company is exhausting. Employees often slack off behind Kelian’s back, so she has to inspect the offices from time to time. Kelian’s company has $n$ offices, numbered from $l$ to $l + n - 1$. Kelian will decide an order in advance and inspect the offices one by one according to this order. At the beginning, all employees in all offices are slacking off. When she finishes inspecting the office with number $i$, the employees in that office start to work hard, and they also notify all offices whose numbers are multiples of $i$ to let them know the boss is here and start working. Therefore, after she finishes inspecting office $i$, all offices whose numbers are multiples of $i$ (including $i$ itself) will have their employees working hard. Kelian discovered this behavior of passing along the message. She found that for every different order $p$, there exists a smallest $t(p)$ such that after she finishes inspecting the first $t(p)$ offices according to this order, all offices will have started working hard. She defines this $t(p)$ as the inspection time of $p$. Kelian wants to know the sum of all $t(p)$. Since the result can be large, she wants the sum modulo $10^9 + 7$.

The first line contains two integers $l, r$ indicating the numbering range. In the problem, $n$ is $r - l + 1$.

Output a single integer, the sum of all $t(p)$.

Sample Explanation Consider all relative orders in which the offices are inspected: {2, 3, 4}, the time is 2. {3, 2, 4}, the time is 2. {4, 2, 3}, the time is 3. {4, 3, 2}, the time is 3. {2, 4, 3}, the time is 3. {3, 4, 2}, the time is 3. The sum is $16$. Constraints - For 20% of the testdata, $r - l + 1 \leq 8$. - For another 10% of the testdata, $l = 1$. - For another 10% of the testdata, $l = 2$. - For another 30% of the testdata, $l \leq 200$. - For 100% of the testdata, $1 \leq l \leq r \leq 10^7$. Translated by ChatGPT 5