<学习笔记>整除分块

\([CQOI2007] 余数求和\)

求 \(G(n,k)=\sum_{i=1}^{n}k \mod i\)

因为 \(k \mod i=k-\lfloor \frac{k}{i}\rfloor*i\)

所以就成了求 \(n*k-\sum_{i=1}^{n}\lfloor \frac{k}{i}\rfloor*i\)

求后者：首先枚举左端点 \(l\)，然后就可以求出左端点所属区间的 \(\lfloor \frac{k}{i}\rfloor\) 设为 \(t\) ,紧接着就可以求出右端点 \(r\) 为 \(k/t\) (因为整除时最大，再大一点 \(t\)会变小) ，计算区间的贡献就是 \((r-l+1)*t*(l+r)* \frac{1}{2}\) 长度 \(\times\) t \(\times\) 区间端点平均值，就可以解决了。