codeforces D. Multiplication Table 二分答案

傷城~ 2022-07-24 08:19 143阅读 0赞

D. Multiplication Table

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted an *n* × *m* multiplication table, where the element on the intersection of the *i*\-th row and *j*\-th column equals *i*·*j* (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the *k*\-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all *n*·*m* numbers from the table in the non-decreasing order, then the *k*\-th number you write out is called the *k*\-th largest number.

Input

The single line contains integers *n*, *m* and *k* (1 ≤ *n*, *m* ≤ 5·105; 1 ≤ *k* ≤ *n*·*m*).

Output

Print the *k*\-th largest number in a *n* × *m* multiplication table.

Examples

input

2 2 2

output

input

2 3 4

output

input

1 10 5

output

Note

A 2 × 3 multiplication table looks like this:

1 2 3
    2 4 6

题意: 有一个n\*m的table, 第i行j列的数字是i\*j, 让你求这个表中第k大的数.

分析: 开始知道使用二分, 然而一直不知道怎么二分. 后来看官方题解才知道..

我们可以二分第k大的数, 然后判断是不是成立, 第k大的数有一个特点, 就是比它小的数一定小于k个, 当比它小的数大于等于k个的时候, 一定不是第k大的数, 有了这个单调性, 我们就可以进行二分了. 二分l=1, r=n\*m, mid = l+r>>1;

检查的时候从每一行开始, 求小于mid的数目((x-1)/row), 把这些数目相加,检查是不是小于k;

但是有一点值得注意, 就是我们二分得到的答案是不是一定存在于n\*m的表中呢? 比如2\*3的表, 5 就不会在表中.

由于我们二分得到的是满足情况的最大值. 如果有一个不在表中, 但是满足比它小的数小于k, 那么他后面一定有一个数满足在表中, 同时满足比它小的数小于k, 再大一些的数就不满足条件了.

#include<bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=100010,MOD=1e9+7;
    ll n,m,k;
    ll check(ll x )
    {
        ll sum=0;
        for(int i=1;i<=n;i++){
            sum += min(m,(x-1)/i);
        }
        return sum;
    }
    int main()
    {
    
        cin>>n>>m>>k;
        ll l=1,r=n*m,ret;
        while(l<=r)
        {
            ll mid=l+r>>1;
            if(check(mid) < k){
                l=mid+1;
                ret=mid;
            }
            else r=mid-1;
        }
        cout<<ret<<endl;
        return 0;
    }