做了一下午……题解都看不懂，最后自己比比划划弄懂了。
题意：给出 \(n,k\)，求 \(\sum\limits_{i=1}^n k \mod i\)。
首先取模形式十分不好处理，所以我们可以根据取模运算定义做一个小小的变换：
\[\sum\limits_{i=1}^n k \mod i = \sum\limits_{i=1}^n k - \left\lfloor \dfrac{k}{i} \right\rfloor \cdot i \]提取出定值 \(k\)，进一步简化为求
\[nk - \sum\limits_{i=1}^n \left\lfloor \dfrac{k}{i} \right\rfloor \cdot i \]我们发现重点在于求 \(\sum\limits_{i=1}^n \left\lfloor \dfrac{k}{i} \right\rfloor \cdot i\)。
我们可以尝试寻找规律，不难发现 \(\left\lfloor \dfrac{k}{i} \right\rfloor\) 的值呈块状分布（即结果数组分成若干块，每块中值相等），这种东西还有另一个名字：整除分块。
首先一个块内部的答案显然是好求的，设块起点为 \(l\)，终点为 \(r\)，则块的贡献为 \(\left\lfloor \dfrac{k}{l} \right\rfloor \cdot \sum\limits_{i=l}^r i\)。
由于第一个块起点已知（\(1\)），第二个块的起点即为第一个块终点加一，所以我们需要快速根据起点求出一个块的重点。
首先由于块内值都相同，可以设 \(x=\left\lfloor \dfrac{k}{l} \right\rfloor=\left\lfloor \dfrac{k}{r} \right\rfloor\)
根据 \(x = \left\lfloor \dfrac{k}{r} \right\rfloor\) 可变形得 \(xr \leq k,r \leq \left\lfloor \dfrac{k}{x} \right\rfloor\)，根据 \(x=\left\lfloor \dfrac{k}{l} \right\rfloor\) 得 \(r \leq \left\lfloor \dfrac{k}{\left\lfloor \dfrac{k}{l} \right\rfloor} \right\rfloor\)
最后分析一下这么做的时间效率：
当 \(i > \sqrt{n}\) 时，\(\left\lfloor \dfrac{k}{i} \right\rfloor \leq \sqrt{n}\) ，也就是说原式只有小于 \(\sqrt{k}\) 种取值。
当 \(i \leq \sqrt{n}\) 时，\(i\) 只有小于 \(\sqrt{k}\) 种取值，也就是说原式也只有小于 \(\sqrt{k}\) 种取值。
所以最多有 \(2 \sqrt{n}\) 个块，我们对于每个块可以 \(o(1)\) 计算，时间可以通过。
标签：lfloor,right,199,题解,rfloor,sqrt,dfrac,left,AcWing From： https://www.cnblogs.com/victoryang-not-found/p/17208391.html