引入
考察定义在正整数集上的函数$f(x)=\left\lfloor \frac a x \right \rfloor $，其中$a$是常正整数，$1\le x \le a$。
取$a=25$，列函数取值如下：
| $x$ | $f(x)$ |
|---|---|
| $1$ | $25$ |
| $2$ | $12$ |
| $3$ | $8$ |
| $4$ | $6$ |
| $5$ | $5$ |
| $6$ | $4$ |
| $7$ | $3$ |
| $8$ | $3$ |
| $9$ | $2$ |
| $10$ | $2$ |
| $11$ | $2$ |
| $12$ | $2$ |
| $13$ | $1$ |
| $14$ | $1$ |
| $15$ | $1$ |
| $16$ | $1$ |
| $17$ | $1$ |
| $18$ | $1$ |
| $19$ | $1$ |
| $20$ | $1$ |
| $21$ | $1$ |
| $22$ | $1$ |
| $23$ | $1$ |
| $24$ | $1$ |
| $25$ | $1$ |
不难发现函数在$x>5$的区间，出现了在多个连续的$x$取值上$f(x)$的值都相等的现象。
再经过思考不难发现，对于任意的$a$，$f(x)$的值域的元素不超过$2\sqrt a$个。原因是：
- 在$1 \le x \le \sqrt a$的范围内，$x$至多有$\sqrt a$个取值，从而$f(x)$至多有$\sqrt a$个取值；
- 在$\sqrt a < x \le a$的范围内，$f(x) \le \left\lfloor \frac {a} {\sqrt a} \right \rfloor \le \sqrt a$，从而$f(x)$至多有$\sqrt a$个取值。
事实上是$f(x)$在$\sqrt a < x \le a$范围内的表现更加吸引我们，因为在这个区间内，$f(x)$表现为一个阶梯函数或分段常函数。对于常数的处理，尤其在求和问题上，要比对函数的处理要方便许多。我们因此希望设计一个算法，找到$f(x)$所有的分段区间，和在每个区间内相应的函数值。如在$a=25$的例子中，我们的算法需要找到：
| $x$ | $f(x)$ |
|---|---|
| $1$ | $25$ |
| $2$ | $12$ |
| $3$ | $8$ |
| $4$ | $6$ |
| $5$ | $5$ |
| $6$ | $4$ |
| $[7,8]$ | $3$ |
| $[9,12]$ | $2$ |
| $[13,25]$ | $1$ |
算法
不难发现，该算法依赖于这样一个问题：对于一个给定的$m$，求最大的$x_0$，使得$f(x_0)=m$。（至于我们为什么不需要求出最小的从而构成一个区间，这将在后面的算法中得到解释。）如在上面的例子中，当$m=3$，$x_0=8$；$m=2$，$x_0=12$；$m=1$，$x_0=25$。
可以通过观察猜想$x_0=\left\lfloor \frac {a} {m} \right \rfloor$，严格证明根据向下取整函数的范围得到，此处略去。
这样，我们可以设计如下算法：
初始情况下$l\leftarrow 1$.
每次令$r\leftarrow \left\lfloor \frac {a} {\left\lfloor \frac {a} {l} \right \rfloor} \right \rfloor$，从而$[l,r]$是函数值为$\left\lfloor \frac {a} {l} \right \rfloor$的区间。在此区间内，将$f(x)=\left\lfloor \frac a x \right \rfloor $视为常数，然后进行相应的计算。注意在这区间上对于任何函数$g$，$g(f(x))=g(\left\lfloor \frac a x \right \rfloor) $也是常数。
令$l\leftarrow r+1$，从而$l$成为下一取值区间的最小值。如此反复，直到$l$超过$a$。
二维分块
刚刚解决了所有关于$\left\lfloor \frac a x \right \rfloor$的函数。那如果函数$h$是关于$\left\lfloor \frac a x \right \rfloor$和$\left\lfloor \frac b x \right \rfloor$的二维函数呢？
其实也是一样的，每次取
$$
r\leftarrow \min \left( \left\lfloor \frac {a} {\left\lfloor \frac {a} {l} \right \rfloor} \right \rfloor , \left\lfloor \frac {b} {\left\lfloor \frac {b} {l} \right \rfloor} \right \rfloor \right)
$$
即可。
例子
给定$n,k$，求
$$
S=\sum_{i=1}^n i \left\lfloor \frac k i \right\rfloor
$$
在每个区间内把$\left\lfloor \frac k i \right\rfloor$看成常数，那么就成了一个简单的等差数列求和。但要注意这里的$k$和$n$的大小关系没有保证，所以代码实现上要考虑一下。
直接上代码了：
1 | ll ans=0; |