SOTSOG学习笔记记录
Posts Notes Algorithms Awesome Tags Categories
SOTSOG学习笔记记录

向下取整数对和

问题描述

对于长度为 $1\le n \le 10^5$ 整数数组 $a$，计算所有的数对 $\lfloor \frac{a_i}{a_j} \rfloor$ 之和，其中 $\lfloor \frac{a_i}{a_j} \rfloor$ 表示向下取整，$0\le i,j \lt n,1\le a_i \le 10^5$，结果对 $10^9+7$ 取余。

示例：

1
2
3
4
5

输入：a = {1, 2, 3}
结果：
a[0] / a[0] + a[0] / a[1] + a[1] / a[2] +
a[1] / a[0] + a[1] / a[1] + a[1] / a[2] +
a[2] / a[0] + a[2] / a[1] + a[2] / a[2] = 1 + 3 + 5 = 9

问题分析

方法一：遍历

最简单的办法就是遍历所有的数对：

1
2
3
4
5
6
7
8

from itertools import product
from typing import List

def pair_floor_sum(a: List[int]) -> int:
    ans = 0
    for x, y in product(a, a):
        ans = (ans + x // y) % 1_000_000_007
    return ans

但是这样的复杂度为 $\mathcal{O}(n^2)$，对于 $10^5$ 的数据会超时。

方法二：整数分块

对于整数 $n$，

  • $\lfloor \frac{n}{i} \rfloor$ 的结果最多只有 $\sqrt{n}$ 数量级个
  • $a=\lfloor \frac{n}{i} \rfloor=\dots=\lfloor \frac{n}{j} \rfloor$ 中 $[i,j]$ 的范围是连续的
  • $j=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$，即如果知道了知道了 $i$，可以在 $\mathcal{O}(1)$ 时间内求出 $j$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from bisect import bisect_left, bisect_right
from typing import List

def pair_floor_sum(a: List[int]) -> int:
    ans = 0
    a.sort()
    for x in a:
        i = 1
        while i <= x:
            j = x // (x // i)
            d = bisect_right(a, j) - bisect_left(a, i)
            ans = (ans + x // i * d) % 1_000_000_007
            i = j + 1
    return ans

时间复杂度为 $\mathcal{m(\sqrt{m}+\log(n))}$，$m$ 为数组中的最大值，虽然二分搜索 $i,j$ 可以通过频率前缀和数组处理 $\mathcal{O}(1)$ 得到，但是还是 $\mathcal{O}(m\sqrt{m})$ 的复杂度，对于 $10^5$ 的数据也会超时。

方法三

对于整数 $x$，

  • $x,x+1,\dots,2x-1$ 除以 $x$ 的结果为 1
  • $2x,2x+1,\dots,3x-1$ 除以 $x$ 的结果为 2
  • $3x,3x+1,\dots,4x-1$ 除以 $x$ 的结果为 3
  • $\cdots$

所以，可以使用一个数组 freq 记录所有数出现的频率，prefreq 记录 freq 的前缀和。

这样对于 $x$，prefreq[2 * x - 1] - prefreq[x - 1] 就表示除以 $x$ 结果为 1 的个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from itertools import accumulate
from typing import List

def pair_floor_sum(a: List[int]) -> int:
    upper = max(a)
    freq = [0] * (1 + upper)
    for x in a:
        freq[x] += 1
    prefreq = list(accumulate(freq))
    ans = 0
    for x in range(1, upper + 1):
        if freq[x]:
            for i in range(x, upper + 1, x):
                d = prefreq[min(upper, i + x - 1)] - prefreq[i - 1]
                ans = (ans + i // x * d * freq[x]) % 1_000_000_007
    return ans

时间复杂度为调和级数的和，复杂度趋近于 $m\log(m)$，$m$ 为数组中的最大值。

方法三与方法二其实原理相同，不过是反过来求。方法二是将数 $x$ 作为分子，方法三是将 $x$ 作为分母，即方法二是求商的个数，方法三是求积的个数。

参考