Description

Link：CF594D

Solution

对于一个质数 $p$，若 $p$ 是区间 $[l, r]$ 中某个数的因数，则欧拉函数还要再乘上 $\frac{p - 1}{p}$。而 $10^6$ 以内，一个数最多只有 $7$ 个质因数。于是我们要数出区间 $[l, r]$ 中作为因数出现的质数 $p$ 所带来的影响。

一开始写了一个简单的莫队，可惜 TLE 了。

考虑扫描线，将所有的询问 $l, r$ 按照右端点 $r$ 从小到大排序。对于一个质数 $p$，设其在区间 $[1, r]$ 中最后一个作为因数出现的位置为 $x$，则只要左端点 $l \leq x$，答案就需要乘上 $\frac{p - 1}{p}$。

于是我们将 $\frac{p - 1}{p}$ 的贡献挂在位置 $x$ 处，询问区间 $[l, r]$ 只需求出区间 $[l, r]$ 的贡献之积即可。使用树状数组维护（树状数组也是可以求前缀积的）。