3056 - 吴壕和熊妹纸不得不说的故事第一季
XMZ这天上课听数学老师讲到了9*9乘法表，于是想到了一个问题，9*9的乘法表中第k小的数是多少呢？于是XMZ去问了WH这个学霸，但是因为XMZ是傲娇的，所以不可能会问这种WH一眼就能看出来的问题，于是XMZ默默的加大了难度把9*9的乘法表变成了n*m的乘法表，这可把WH难倒了，为了不在自己的女神面前丢脸，WH不得不来请教你们。
输入 n, m, k。问在 n*m 的乘法表中第 k 小的数是多少，重复的数算多个。
Input
输入包含多组测试数据。每组测试数据占一行。每行包含三个正整数 n, m, k。1≤n,m≤10^6; 1≤k≤n*m
Output
每组数据输出一行。每行包含一个整数表示 n*m 的乘法表中第 k 小的数。
Examples
Input
1 10 5 2 3 4
Output
5 3
Hint
2*3 的乘法表为
1 2 3
2 4 6
其中第 4 小的数是 3。重复的 2 各算一个。<br />
Solution 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; }
Hint
2*3 的乘法表为
1 2 3
2 4 6
其中第 4 小的数是 3。重复的 2 各算一个。
<br />