题目描述

给定一个 n×m 的方格矩阵，每个方格内都有一个整数元素。

其中第 i 行第 j 列的方格中的元素为 i×j（行和列都从 1 开始编号）。

现在，需要你将这 n×m 个整数按照非严格单调递增的顺序一一写出。

请问，你写出的第 k 个整数是多少。

输入格式
一行，三个整数 n,m,k。

输出格式
一行，输出你写出的第 k 个整数。

数据范围
前 6 个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n,m≤5×105，1≤k≤n×m。

样例

cin:
2 2 2
cout:
2

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m;
LL k;
LL check(LL mid){
    LL cnt = 0;
    for(LL i = 1; i <= n; i ++ ){
        cnt += min(m, mid / i);
    }
    return cnt;
}
int main()
{
    cin >> n >> m >> k;
    int s = min(n, m);
    LL l = 0, r =  n * m;
    while(l < r){
        LL mid = l + r + 1>> 1;
        if(check(mid) < k) l = mid;
        else r = mid - 1;
    }
    cout<<l+1;
    return 0;
}