洛谷 CF448D Multiplication Table

目录

• $code$

---

题目

cf448d multiplication table

思路

二分答案，每一排都是递增的，所以二分$ans$，去计算有多少个数和$ans$相等，有多少个数比$ans$小，如果小于$ans$的数少于$k$个并且小于等于$ans$的数大于等于$k$个，那么当前$ans$就是答案。
q：如何计算$ans$小的数的个数？
a：
$$\sum_{i=1}^{n}(min(\lfloor \frac{ans-1}{i} \rfloor,m))$$

$code$

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m,k;
inline void read(ll &t){
    ll x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    t=f?-x:x;
}

int main(){
    read(n),read(m),read(k);
    ll l=1,r=n*m,ans;
    while(l<r){
        ll mid=(l+r)>>1,sum=0,tmp=0;
        for(int i=1;i<=n;++i){
            sum+=min(m,(mid-1)/i);
            if(sum%i==0&&sum/i<=m) tmp++;
        }
        if(sum<k&&sum+tmp>=k){
            ans=mid;
            break;
        }
        if(sum+tmp<k) l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}