D. Multiplication Table - 题解

比赛与标签

比赛: Codeforces Round 256 (Div. 2) 标签: binary search, brute force 难度: *1800

喵喵，这是什么任务呀？

主人，你好喵~ Bizon the Champion 真是个聪明的家伙，我们也要像他一样快地解决问题才行！(๑•̀ㅂ•́)و✧

这道题是这样的呐：

我们有一个 n x m 的乘法表，表格里第 i 行第 j 列的数字就是 i * j。然后呢，我们需要把这 n * m 个数字全部拿出来，按照从小到大的顺序排成一排。我们的任务就是找出这个排好序的数列中，第 k 个数字是多少。

举个栗子，如果 n=2, m=3，乘法表就是：

1 2 3
2 4 6

把所有数字排好序就是：1, 2, 2, 3, 4, 6。如果 k=4，那么第 4 小的数字就是 3 啦！

让我想想怎么做最快喵！

喵~ 最直接的想法就是真的建一个 n*m 的数组，把所有 i*j 的结果存进去，然后排序找第 k 个。但是 n 和 m 最大有 5*10^5，n*m 会超级大，内存和时间都会爆炸的，不行不行喵！必须想个更聪明的办法。

既然不能直接求，那我们可不可以猜一个答案 x，然后看看它是不是我们想要的呢？这种“猜答案再验证”的思路，最适合用二分查找了喵！

我们是在对答案的值进行二分。答案可能的范围是什么呢？最小是 1*1=1，最大是 n*m。所以我们的搜索区间就是 [1, n*m]。

二分的核心思路

二分的核心就是要有一个 check 函数。对于我们猜的答案 mid，我们需要知道什么信息才能判断它和真实答案的关系呢？

我们可以问一个关键问题：在这个 n x m 的乘法表里，有多少个数是小于等于 mid 的呢？ 我们把这个数量记作 count。

然后根据 count 和 k 的关系来调整二分范围：

如果 count >= k：这说明什么呢？说明小于等于 mid 的数已经有至少 k 个了。那真正的第 k 小的数，要么就是 mid，要么比 mid 还要小。所以我们可以大胆地把搜索范围缩小到 [left, mid]，去尝试更小的值，喵~
如果 count < k：那说明小于等于 mid 的数还不够 k 个。真正的第 k 小的数肯定比 mid 要大。所以我们就得在 [mid + 1, right] 这个范围里继续找啦。

通过不断地这样缩小范围，left 和 right 最终会相遇，相遇的地方就是我们苦苦寻找的最小的、满足“小于等于它的数不少于k个”的那个数，也就是我们的答案啦！

如何快速计算 `count` (最关键的一步喵！)

现在的问题就变成了：如何快速计算出乘法表里有多少个数小于等于我们猜的 x (也就是mid) 呢？

我们一行一行地看：对于第 i 行，它的元素是 i*1, i*2, ..., i*m。我们要找有多少个列 j ( 1 <= j <= m ) 满足 i * j <= x。这个不等式稍微变一下就是 j <= x / i (这里是整数除法哦)。所以，在第 i 行，小于等于 x 的数的个数就是 min(m, x / i) 个！因为列数 j 最多不能超过 m 嘛。

一个简单的方法是，我们用一个循环从 i=1 到 n，把每一行的 min(m, x / i) 加起来。这个方法的时间复杂度是 O(n)。整个二分查找就是 O(n * log(nm))。对于这道题的数据范围，这个复杂度是可以通过的！

代码里的黑魔法：整除分块喵！

但是，我们提供的AC代码用了一个更快的技巧，叫做**“整除分块”**（也叫数论分块），喵~

我们观察到，当 i 在某个范围内连续变化时，x / i 的值可能是不变的。比如 x=10，当 i 是 6, 7, 8, 9, 10 的时候，10 / i 的值都是 1！

我们可以把 x / i 值相同的那些行 i 一起计算，这样就不用一行一行地加了！

对于当前的行 i，我们计算出 q = x / i。
然后我们找到最大的行号 j，使得 x / j 的值也等于 q。可以证明，这个 j 其实就是 min(n, x / q)。
那么，所有从 i 到 j 的行，它们小于等于 x 的元素个数都是 min(m, q)。
这样，我们一次就可以计算 (j - i + 1) 行的结果，然后下一次直接从 j + 1 行开始。这个方法的复杂度大约是 O(sqrt(n)) 级别的，比 O(n) 快很多呢！

来写代码啦喵~

cpp

#include <iostream>
#include <algorithm>

using namespace std;

/**
 * @brief 计算乘法表中不大于 x 的数的个数，使用了整除分块优化喵~
 * @param x 我们要检查的数值 (也就是二分查找中的 mid)
 * @param n 表格的行数
 * @param m 表格的列数
 * @return 小于等于 x 的数的总个数
 */
long long countNumbers(long long x, long long n, long long m) {
    long long cnt = 0;
    long long i = 1;
    // 使用整除分块来加速计算
    while (i <= n) {
        // 如果 x 比当前行号还小，那这一行和后面的行肯定没有任何数小于等于 x 了
        if (x < i) 
            break;
        
        // 对于第 i 行，最多有 q = x / i 列的数是小于等于 x 的
        long long q = x / i;
        
        // 找到最大的行号 j，使得 x/j 的值与 x/i 相同。
        // 这个 j 就是 min(n, x/q)。所有 i 到 j 行的 q 值都一样。
        long long j = min(n, x / q);
        
        // 如果计算出的列数 q 超过了总列数 m，那说明这些行都贡献了 m 个数
        if (q >= m) {
            cnt += (j - i + 1) * m;
        } else {
            // 否则，这些行都贡献了 q 个数
            cnt += (j - i + 1) * q;
        }
        
        // 跳到下一个块的开头
        i = j + 1;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m, k;
    cin >> n >> m >> k;

    // 二分查找的范围是 [1, n*m]
    long long low = 1;
    long long high = n * m;
    
    // 寻找最小的 x，使得 countNumbers(x) >= k
    while (low < high) {
        long long mid = low + (high - low) / 2; // 用这种写法防止溢出，好习惯喵~
        
        // 计算小于等于 mid 的数的个数
        long long cnt = 0;
        // 这里可以直接用一个 O(n) 的循环，也能过
        // 为了和上面的函数对应，我们也可以调用 countNumbers
        // for (long long i = 1; i <= n; ++i) {
        //     cnt += min(m, mid / i);
        // }
        cnt = countNumbers(mid, n, m);

        if (cnt >= k) {
            // mid 可能就是答案，或者答案在 mid 左边
            high = mid;
        } else {
            // mid 太小了，答案在 mid 右边
            low = mid + 1;
        }
    }

    cout << low << endl;

    return 0;
}

复杂度分析

时间复杂度: O(sqrt(n) * log(n*m)) 的说。我们的 countNumbers 函数使用了整除分块技巧，它的时间复杂度是 O(sqrt(n)) 的说（更精确地说是 O(min(n, sqrt(x)))，但 i 只到 n，所以可以看作 O(sqrt(n))）。外面套了一层二分查找，范围是 n*m，所以二分部分是 O(log(n*m))。总的时间复杂度就是 O(sqrt(n) * log(n*m))，非常快喵！即使不用整除分块，O(n * log(n*m)) 也是能通过的。
空间复杂度: O(1) 的说。我们只用了几个变量来存储 n, m, k 和二分查找的边界，没有用额外的数组，所以空间复杂度是 O(1) 的说，非常节省内存呐！

知识点与总结

这次我们学到了很多有用的东西喵！

二分答案 (Binary Search on Answer): 这是这道题的核心思想！当问题是求“第k大/小”、“最大值的最小值”、“最小值的最大值”这类问题，并且答案具有单调性时，就可以考虑二分答案喵~
单调性: 这里的单调性就是：如果一个数 x 满足条件（小于等于它的数不少于k个），那么所有比 x 大的数也一定满足条件。这是我们能用二分的基础！
整除分块 (Division Block): 这是一个很酷的数论优化技巧！当我们需要计算形如 sum(floor(N/i)) 的式子时，就可以用它来加速，把 O(N) 的复杂度降到 O(sqrt(N))。以后遇到类似的求和可以试试看喵！
64位整数 (long long): 注意 n*m 可能会超过 int 的范围（大约 2*10^9），而 5*10^5 * 5*10^5 是 2.5*10^{11}，所以一定要用 long long 来存储，不然会溢出WA掉的，要小心哦！

多练习这样的题目，你也会变得和 Bizon a Champion 一样厉害的，加油喵~！(ゝ∀･)

D. Multiplication Table - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ ​

让我想想怎么做最快喵！ ​

二分的核心思路 ​

如何快速计算 count (最关键的一步喵！) ​

代码里的黑魔法：整除分块喵！ ​

来写代码啦喵~ ​

复杂度分析 ​

知识点与总结 ​