（太菜了，群友指点两小时才过） 按套路，将取模拆开，式子变成： ⨁ i = 1 n ( n − i ∗ ⌊ n i ⌋ ) \displaystyle\bigoplus_{i = 1}^n (n - i*\lfloor\frac{n}{i}\rfloor) i=1⨁n(n−i∗⌊in⌋) 然后就可以按套路，按位考虑，计算每一位为 1 的数字的个数： ∑ i = 0 n ⌊ n − ⌊ n i ⌋ ∗ i 2 p ⌋ \displaystyle\sum_{i = 0}^{n}\lfloor\frac{n - \lfloor\frac{n}{i}\rfloor*i}{2^p}\rfloor i=0∑n⌊2pn−⌊in⌋∗i⌋ 对 ⌊ n i ⌋ \lfloor\frac{n}{i}\rfloor ⌊in⌋进行分块，每个块间套类欧几里得，复杂度是 n log 2 n \sqrt n \log^2n n log2n。
⌊ n i ⌋ \lfloor\frac{n}{i}\rfloor ⌊in⌋ 分块在 i 较小时块比较小，块比较密集，对这些小的块可以直接暴力求解以降低常数，暴力到 4 e 7 4e7 4e7左右可以跑得飞快。
另一个小优化：对块间求类欧时，不需要每次都用 s o l v e ( r ) − s o l v e ( l − 1 ) solve(r) - solve(l - 1) solve(r)−solve(l−1)，将式子改一下： ∑ i = 0 r − l ⌊ n − ⌊ n i ⌋ ∗ ( i + l ) 2 p ⌋ \displaystyle\sum_{i = 0}^{r - l}\lfloor\frac{n - \lfloor\frac{n}{i}\rfloor*(i + l)}{2^p}\rfloor i=0∑r−l⌊2pn−⌊in⌋∗(i+l)⌋
这样直接 s o l v e ( r − l + 1 ) solve(r - l + 1) solve(r−l+1)即可，可以略微降低一些时间。
对于这题的类欧形式 a a a 是负的，若 a,b有负数，需要将 a ，b转正。 a ∗ x + b c , a ∗ x + b \frac{a*x + b}{c},a*x + b ca∗x+b,a∗x+b 本质上是一个等差数列，计算尾项然后把整个数列倒过来 a 就转正了，但倒过来之后 b 也可能是负数（以至于前几项都是负数），我用的究极笨比方法这时数列其实分成正负两部分，负数那部分可以倒过来，全部变成正的然后减掉那部分的贡献即可（那部分的贡献是负数） 详细见代码
