P3601 Check-in Problem

This is a check-in problem. It is recommended to carefully read the Constraints before solving.

We define a function $\operatorname{qiandao}(x)$ as the number of integers less than or equal to $x$ that are not coprime with $x$. Given $l$ and $r$, compute: $$\sum_{i=l}^r \operatorname{qiandao}(i)\bmod 666623333.$$

One line with two integers, $l$ and $r$.

One line with one integer representing the answer.

- For 30% of the testdata, $l,r\leq 10^3$. - For 60% of the testdata, $l,r\leq 10^7$. - For 100% of the testdata, $1 \leq l \leq r \leq 10^{12}$, $r-l \leq 10^6$. Translated by ChatGPT 5