[CF][二分查找][×] codeforces 448D Multiplication Table

写这个题为了提醒自己先想简单的做法再想复杂的，不要一上来就跑偏到复杂操作上去。。。

题目要求给出n*m的乘法表中第K大的元素，n和m都是5e5数量级. 暴力显然不行，所以得找个快速的方法分辨出第k大，然后我由于这几天一直在搞数论，脑子抽了从质因数分解的角度考虑结果弄得巨复杂。。。最后看官方题解就一句话二分查找，醍醐灌顶。。。

由于生成表格的方法是i*j所以check只要把所有的x/i加和与k比较大小就是了。

wa点是这个x/i可能会大于m所以要二者取min，然后另外一点是有很多重复的结果导致这个二分是不一定能准确的定位到是哪一个的，所以要判断-1和+1的情况。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int maxn = 1e6+5;
const int mod = 1e9 + 7;

LL n,m,k;
bool check(LL x)
{
    LL res=0;
    for(int i=1;i<=n;i++)
    {
        res+= min(m,x/i);
    }
    if(res>=k) return 1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    cin>>n>>m>>k;
    LL ans=n*m;
    LL l=1,r=n*m,m;
    while(l<r)
    {
        m=(l+r)>>1LL;
        //cout<<m<<endl;
        if(check(m)) r=m;
        else l=m+1;
    }
    if(check(l-1))
    {
        cout<<l-1;
    }
    else if(check(l))
    {
        cout<<l;
    }
    else if(check(l+1))
    {
        cout<<l+1;
    }
    return 0;
}