首页 > 代码库 > Codeforces Round #256 (Div. 2) Multiplication Table

Codeforces Round #256 (Div. 2) Multiplication Table

刚刚开始想到一种很暴力但还行的方法,不过在和TK讨论的过程中引出了一个更好的算法

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;long long n,m,k;long long check(long long x){    long long ans=0;    for(int i=1;i<=n;i++)    {        ans+=min(x/i,m);        if(min(x/i,m)*i==x)            ans--;    }    return ans;}int main(){    scanf("%I64d%I64d%I64d",&n,&m,&k);    long long l=1,r=n*m+3;    long long ans=0;    while(l<r)    {        long long mid=(l+r)>>1;        long long a=check(mid);        long long b=check(mid+1);        if(a<k&&b>=k)        {            ans=mid;            break;        }        else if(b<k)l=mid;        else if(a>=k)r=mid;    }    cout<<ans<<endl;}
View Code