（题解里面好像都没怎么讨论复杂度）

假设区间长度为 $m$ （本题为 $10^6$）, $R_{max}$ 为 $n$ （本题为 $2^{31}$）

预处理的复杂度就是 $O(\sqrt n)$ ，后半部分的复杂度通过下式计算： $\sigma(n) = \sum_{d \le {\sqrt n} \; and \; d \ is \ prime} \frac{m}{d} = m\sum_{d \le {\sqrt n} \; and \; d \ is \ prime} \frac{1}{d}$

$\sum_{i=1}^{n}\frac{1}{i}$ 是 $\ln{n}$ 量级的，而素数的密度 $\frac{1}{\ln{n}}$不过貌似并没有什么用，$\sigma(n)$本地测试貌似是 $O(\ln n)$的。

所以总复杂度是不是 $O(\sqrt n + m \ln n)$ ？

换而言之n, m都可以再大一点把MR卡掉（