签到题

题目描述

这是一道签到题！

建议做题之前仔细阅读数据范围！

我们定义一个函数：$\operatorname{qiandao}(x)$ 为小于等于 $x$ 的数中，与 $x$ 不互质的数的个数。

这题作为签到题，给出 $l$ 和 $r$，求出：

$$\sum_{i=l}^r \operatorname{qiandao}(i)\bmod 666623333$$

输入格式

一行两个整数，$l$、$r$。

输出格式

一行一个整数表示答案。

233 2333

1056499

2333333333 2333666666

153096296

提示

- 对于 $30\%$ 的数据，$l,r\leq 10^3$。 - 对于 $60\%$ 的数据，$l,r\leq 10^7$。 - 对于 $100\%$ 的数据，$1 \leq l \leq r \leq 10^{12}$，$r-l \leq 10^6$。 标签: P3601|数学|洛谷原创|O2优化|洛谷月赛|欧拉函数

来源

P3601|签到题