# 数论分块

对于包含了向下取整的除法式，例如$\sum_{i=1}^{n}\lfloor \cfrac{n}{f(x)}\rfloor$ 这样的算式，直接从$1$ 到$n$ 去枚举计算显然效率是比较低的。而数论分块也就给予了可以快速计算的方法。

我们可以注意到向下取整式有这样的性质：

$$\forall a,b,c\in\mathbb{Z},\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor$$

通过上面的性质，我们可以得到下面的结论：

定理（数论分块）: 对于常数$n$ 和一个$i\le n$，使得

$$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$$

成立的最大的$j(i\le j\le n)$ 为$\lfloor\cfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$。

证明过程说实话有些偏。

这个定理说明了这样的一个问题，例如我们要计算$\sum_{i=1}^nf(x)\lfloor\cfrac{n}{i}\rfloor$ 的时候，如果计算$f(x)$ 前缀和即$s(i)=\sum_{j=1}^if(j)$ 的时间复杂度并不高，那么我们可以快速的计算这个和式：对于$i$，我们找到满足$\lfloor\cfrac{n}{i}\rfloor=\lfloor\cfrac{n}{j}\rfloor$ 的最大的$j=\lfloor\cfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$，那么$\sum_{k=i}^nf(x)\lfloor\cfrac{n}{k}\rfloor=\lfloor\cfrac{n}{i}\rfloor\cdot(s(j)-s(i))$。

以这个题目为例：

给出正整数$n$ 和$k$，计算：

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

数据范围为$10^9$，在 OI 的时限内使用$O(n)$ 的算法必然是不现实的。

我们考虑到$a\mod b=a-\lfloor\cfrac{a}{b}\rfloor\cdot b$，那么上式可以转换为：

$$G(n,k)=\sum_{i=1}^n{k-\lfloor\cfrac{k}{i}\rfloor\cdot i}$$

这样子式子就被转换成了数论分块能够解决的形式。

显然$\sum_{i=1}^nk$ 是容易计算的，同时函数$f(i)=i$ 的前缀和也非常容易计算，通过数论分块我们能够快速解决这个问题。

不过这道题这边有些不一样，求和的上界是$n$ 而处于向下取整分子上的是$k$。我们可以加入判断，如果$k>n$，那么枚举到$i>n$ 的时候自然停止就可以，而如果$n>k$，那么在$i>k$ 的时候自然停止就可以，因为后面的$\lfloor\cfrac{k}{i}\rfloor\cdot i=0$，没有必要计算。故我们循环终止的条件是$i>\min(n,k)$。

这样，这道题就可以解决了！

def suf_sum(i):

    # 计算前缀和，实际上就是等差数列求和

    return (1 + i) * i // 2

def main(n, k):

    sum = n * k

    l = 1

    while l <= min(n, k): # 边界条件

        r = k // (k // l)

        # 寻找这个分块的右边界

        if r > min(n, k):

            # 注意特判超出边界的情况

            r = min(n, k)

        sum -= (suf_sum(r) - suf_sum(l - 1)) * (k // l)

        l = r + 1

    return sum

if __name__ == '__main__':

    n, k = map(int, input().split())

    print(main(n, k))

# 参考资料

[1] https://oi-wiki.org/math/number-theory/sqrt-decomposition/

[2] https://www.luogu.com.cn/problem/P2261