首页计算机科学算法数论算法

# 数论分块

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

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

∀a,b,c∈Z,⌊abc⌋=⌊⌊ab⌋c⌋\forall a,b,c\in\mathbb{Z},\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor

证明

向下取整实际上可以写成这样的形式：

a=⌊a⌋+r (0≤r<1)a=\lfloor a\rfloor+r\ (0\le r<1)

因此上面式子带入之后可以得到：

⌊abc⌋=⌊1c⋅ab⌋=⌊1c⋅(⌊ab⌋+r)⌋=⌊1c⌊ab⌋+rc⌋=⌊1c⌊ab⌋⌋□\begin{aligned} \lfloor\frac{a}{bc}\rfloor&=\lfloor{\frac{1}{c}\cdot\frac{a}{b}}\rfloor&\\&=\lfloor{\frac{1}{c}\cdot(\lfloor\frac{a}{b}\rfloor+r)}\rfloor&\\ &=\lfloor \frac{1}{c}\lfloor\frac{a}{b}\rfloor+\frac{r}{c}\rfloor&\\&=\lfloor \frac{1}{c}\lfloor\frac{a}{b}\rfloor\rfloor&\\ &&\square \end{aligned}

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

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

⌊ni⌋=⌊nj⌋\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor

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

证明过程说实话有些偏。

证明

设k=⌊ni⌋k=\lfloor\cfrac{n}{i}\rfloor，有k≤⌊ni⌋k\le\lfloor\cfrac{n}{i}\rfloor。

而⌊nk⌋≥⌊n⌊ni⌋⌋=⌊i⌋=i\lfloor\cfrac{n}{k}\rfloor\ge\lfloor\cfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=\lfloor{i}\rfloor=i，故有j=imax=⌊n⌊ni⌋⌋.j=i_{max}=\lfloor\cfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor.

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

以这个题目为例：

给出正整数nn 和kk，计算：

G(n,k)=∑i=1nkmod  iG(n,k)=\sum_{i=1}^n{k\mod i}

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

我们考虑到amod  b=a−⌊ab⌋⋅ba\mod b=a-\lfloor\cfrac{a}{b}\rfloor\cdot b，那么上式可以转换为：

G(n,k)=∑i=1nk−⌊ki⌋⋅iG(n,k)=\sum_{i=1}^n{k-\lfloor\cfrac{k}{i}\rfloor\cdot i}

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

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

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