整除分块学习笔记整除分块学习笔记

整除分块学习笔记值域分段求和假如我们要对这样的式子进行求和：

\[\sum\limits_{i=1}^{n} f(i) \]
如果 \(f(i)\) 的取值有限，只有 \(m\) 个，且对于所有的 \(f(i)=x\) 在序列中都是连续的一段，那么就可以进行值域分段求和。
找出每个取值 \(x\) 在原序列中的第一次出现的位置 \(L_x\) 和最后一次出现的位置 \(R_x\)，可以在 \(O(m)\) 的时间内算出答案（设 \(v_1,v_2\dots v_m\) 为 \(f(i)\) 的 \(m\) 种取值）：

\[Ans=\sum\limits_{i=1}^{m}(R_i-L_i+1)v_i \]
例如：

\[\sum\limits_{i=1}^{n}\lfloor{log_2i}\rfloor \]
设 \(f(i)=\lfloor{log_2i}\rfloor\)，容易发现 \(0\le f(i) \le log_2n\) 且单调递增。运用上述方法，可计算出 \(L_x=2^x,R_x=2^{x+1}-1\)，于是可以在 \(O(logn)\) 的时间内求解：

\[Ans=\sum\limits_{i=1}^{\lfloor{log_2(n)}\rfloor}2^ii \]
整除分块整除分块就是依据整除的性质，对取值种类只有 \(\sqrt n\) 级别的 \(f\) 序列进行的值域分段求和。
举几个简单的例子：

\[\sum\limits_{i=1}^{n}\lfloor{\frac{n}{i}}\rfloor \]
设 \(f(i)=\lfloor{\frac{n}{i}}\rfloor\)，则 \(f(i)\) 的取值不超过 \(2\sqrt n\) 种且单调递增。运用上述方法，可计算出 \(L_x=\lfloor\frac{n}{\lfloor\frac{n}{x-1}\rfloor}\rfloor+1,R_x=\lfloor\frac{n}{\lfloor\frac{n}{x}\rfloor}\rfloor\)，值域分段求和即可，时间复杂度 \(O(\sqrt{n})\)。
代码片段：

for(int l=1,r=0; l<=n; ) { l=r+1,r=n/(n/l); ans+=(n/l)*(r-l+1); }

\[\sum\limits_{i=1}^{n}i^2\lfloor{\frac{n}{i}}\rfloor \]
设 \(f(i)=\lfloor{\frac{n}{i}}\rfloor\)，仍然有 \(L_x=\lfloor\frac{n}{\lfloor\frac{n}{x-1}\rfloor}\rfloor+1,R_x=\lfloor\frac{n}{\lfloor\frac{n}{x}\rfloor}\rfloor\)。考虑对于每一段 \([L_x,R_x]\) 计算答案的贡献：
\(\sum\limits_{i=L_x}^{R_x}i^2x\)
\(=x\sum\limits_{i=L_x}^{R_x}i^2\)
\(=x(\sum\limits_{i=1}^{R_x}i^2-\sum\limits_{i=1}^{L_x-1}i^2)\)
\(=x(\frac{R_x(R_x+1)(2R_x+1)}{6}-\frac{L_x(L_x+1)(2L_x+1)}{6})\)
然后就可以 \(O(\sqrt n)\) 求解了。
【整除分块学习笔记】代码片段：