题解 | #小红的矩阵# (数论分块优化循环)

二分遍历(O(nlog(n*m)) 思路可以参考其他题解, 此题解思路在此基础上进行了一点升级, 使用了数论分块加速

我们观察二分的 check 函数, 其返回值为:

$check(x) = \Sigma_{i=1}^nmin(m, \lfloor \frac{x}{i} \rfloor)$

注意到计算 $\Sigma \lfloor \frac{x}{i} \rfloor$ 是数论分块的经典问题

因此我们 check 函数的遍历可以使用数论分块思路加速

数论分块思路简单来说, 就是根据 $\lfloor \frac{x}{i} \rfloor$ 的值给 i 分组, 同组的 i 具有相同的 $\lfloor \frac{x}{i} \rfloor$ 的结果
因此我们只需要知道每组内有多少个 i, 就能按组得出结果
更详细的内容请去 oi-wiki 上的查看

下面是数论分块一个简单的例子

假设 x = 6

i	1	2	3	4	5	6
$\lfloor \frac{x}{i} \rfloor$	6	3	2	1	1	1

$res = 6*1 + 3*1 + 2*1 + 1*3$

可以发现 i = 4, 5, 6 的时候, 结果都是 1, 所有如果我们可以快速知道每组的左右边界, 那么每组就可以 O(1) 算出结果

幸运的是, 我们同样可以 O(1) 算出每组的左右边界

假如我们知道该组的左边界 l, 那么有边界可以按下面式子算出

$r = \lfloor \frac{x}{\lfloor x/l \rfloor} \rfloor$

最终时间复杂度大概在 $O(logn * log(n*m))$

ps. 最后注意下边界处理即可

#include <bits/stdc++.h>
#define i64 long long
using namespace std;

i64 n, m, k;
i64 check(i64 tar){
    i64 t = tar / m;
    i64 res = t * m;

    for(i64 l = t+1;l<=n;){
        i64 ct = tar / l;
        if(ct == 0) break;

        i64 r = min(tar / ct, n);
        res += (r-l+1)*ct;
        l = r+1;
    }

    return res;
}

int main() {
    cin>>n>>m>>k;
    i64 l = 1, r = n*m;
    while(l+1<r){
        i64 mid = l+r>>1;
        if(check(mid) >= k) r = mid;
        else l = mid;
    }

    cout<<r<<endl;
}

// int main() {
//     int n, m;
//     cin>>n>>m;
//     vector<vector<int>> g(n, vector<int>(m));
//     for(int i = 0;i<n;i++){
//         for(int j = 0;j<n;j++){
//             g[i][j] = (i+1) * (j+1);
//         }
//     }

//     for(int i = 0;i<n;i++){
//         for(int j = 0;j<n;j++){
//             cout<<g[i][j]<<" ";
//         }
//         cout<<endl;
//     }
// }
// 64 位输出请用 printf("%lld")