游客 注册 | 登录
中文 | En

3056 - 吴壕和熊妹纸不得不说的故事第一季

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

XMZ这天上课听数学老师讲到了9*9乘法表，于是想到了一个问题，9*9的乘法表中第k小的数是多少呢？于是XMZ去问了WH这个学霸，但是因为XMZ是傲娇的，所以不可能会问这种WH一眼就能看出来的问题，于是XMZ默默的加大了难度把9*9的乘法表变成了n*m的乘法表，这可把WH难倒了，为了不在自己的女神面前丢脸，WH不得不来请教你们。

输入 n, m, k。问在 n*m 的乘法表中第 k 小的数是多少，重复的数算多个。

题目输入

输入包含多组测试数据。每组测试数据占一行。每行包含三个正整数 n, m, k。1≤n,m≤10^6; 1≤k≤n*m

题目输出

每组数据输出一行。每行包含一个整数表示 n*m 的乘法表中第 k 小的数。

输入/输出样例

输入格式

1 10 5
2 3 4

输出格式

5
3

C++解答

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cfloat>
#include<climits>
#include<cmath>
#include<cstdio>

using namespace std;

int main()
{
  long long n,m,k;
  while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
  {
    long long l=0,r=n*m;
    bool tag=0;
    while(!tag)
    {
      long long res=0;
      long long mid=(l+r)>>1;
      long long now=m;
      long long res1=0;
      for(long long i=1;i<=n;i++)
      {
        for(;now>=1;now--)
        {
          if(i*now<mid)
          {
            res+=now;
            break;
          }
          else if(i*now==mid)
          {
            res1++;
            res+=now-1;
            break;
          }
        }
      }
      if(k>res&&k<=res+res1)
      {
        printf("%lld\n",mid);
        tag=1;
      }
      else if(k<=res)
        r=mid;
      else l=mid+1;
    }
  }
  return 0;
}
请先登陆