例题一
\[\sum_{i=1}^n \lfloor\frac n i\rfloor\\ \]首先很容易想到直接求解，对于较大的数据，\(O(n)\)做法无法通过。
注意到函数\(y=\lfloor\dfrac n x\rfloor\)的图像如下：
不难发现，随着 \(x\) 增大 ，\(y\)单调不增，这说明对于相同值的 \(y\) 总是分布在同一块区域。
这启发我们根据\(y\)值，把\(x\)分组，每组“打包”算好。
这个时间复杂度显然是 \(O(\sqrt n)\)的，时间复杂度与\(\lfloor\dfrac n x\rfloor\)的数量有关，这个数量大概是\(2\sqrt n\)。
虽然图像上看\(y\)的数量很大，但是考虑到许多\(y\)不包含整数的\(x\),因此时间复杂度就是这样的了。
代码实现如下：
for(LL l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans+=(n/l)*(r-l+1);
}
例题二
\[\sum_{i=1}^nk\bmod i\\ \]对原式进行推导：
\[\sum_{i=1}^nk\bmod i\\ =\sum_{i=1}^nk-i\lfloor\frac k i\rfloor\\ =nk-\sum_{i=1}^ni\lfloor\frac k i\rfloor\\ \]后面的部分可以用整除分块解决，对于每个\(\lfloor \dfrac n i\rfloor\),内部相当于一个等差数列。
代码实现如下：
ans=n*k;
for(LL l=1,r;l<=n&&l<=k;l=r+1)
{
r=min(k/(k/l),n);
ans-=(k/l)*(r+l)*(r-l+1)/2;
}
例题三
函数 \(f(i)\) 表示 \(i\) 所有约数的和。
求 \(\sum\limits_{i=L}^R f(i)\)。
考虑前缀和作差，问题变成\([1,R]-[1,L-1]\)。
于是不难列出式子求解，与上一题很像。
例题四
\[\sum_{i=1}^n\sum_{j=1}^m (n\bmod i)(m\bmod j)\\ \]这道题显然也是推导。
\[\sum_{i=1}^n\sum_{j=1}^m (n\bmod i)(m\bmod i)\\ =\sum_{i=1}^n(n\bmod i)\sum_{j=1}^m (m\bmod j)\\ =\sum_{i=1}^n(n-i\lfloor\frac n i\rfloor)\sum_{j=1}^m (m-j\lfloor\frac m j\rfloor)\\ =(n^2-\sum_{i=1}^n i\lfloor\frac n i\rfloor)(m^2-\sum_{j=1}^m m\lfloor\frac m j\rfloor)\\ \]左右两边分开计算即可。
例题五
\[\sum_{i=1}^n (n\bmod i)(m\bmod i)\\ \]和上道题看着很像，不过这道题就很复杂了。
\[\sum_{i=1}^n (n\bmod i)(m\bmod i)\\ =\sum_{i=1}^n (n-i\lfloor\frac n i\rfloor)(m-i\lfloor\frac m i\rfloor)\\ =\sum_{i=1}^n (nm-(n+m)i\lfloor\frac n i\rfloor+i^2\lfloor\frac n i\rfloor\lfloor\frac m i\rfloor)\\ =n^2m-(n+m)\sum_{i=1}^n i\lfloor\frac n i\rfloor+\sum_{i=1}^n i^2\lfloor\dfrac n i\rfloor\lfloor\frac m i\rfloor\\ \]前面的式子我们已经可以轻松求出了，对于后面的这个东西，我们还是画图观察：
显而易见，仍然满足我们刚开始的两个性质，因此依旧使用之前的方式进行整除分块，时间复杂度依旧是\(O(\sqrt n)\)。
具体思想如下：
我们的值变化，要么是因为 \(\lfloor\dfrac n x\rfloor\) 变化了，要么是因为 \(\lfloor\dfrac m x\rfloor\) 变化了。
因此找出 \(\lfloor\dfrac n x\rfloor\) 变化的点和 \(\lfloor\dfrac m x\rfloor\) 变化的点中最近的一个，作为我们的 \(r\) 值。
后面部分的代码实现如下：
for(LL l=1,r=0;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans=ans+(n/l)*(m/l)*(sum(r)-sum(l-1));
}
这里出现了一个函数，它的作用是求出：\(sum_i=\sum\limits_{i=1}^ni^2\)。
公式是 \(\sum\limits_{i=1}^ni^2=\dfrac {n(n+1)\times(2n+1)} 6\)，用数学归纳法很好证明，这里不多赘述了。
标签：lfloor,frac,浅谈,分块,dfrac,sum,rfloor,整除,bmod From： https://www.cnblogs.com/dengduck/p/17382929.html