題目描述
度度熊和爺爺在玩一個(gè)乘法表游戲。乘法表的第i行第j列位置的元素為ij，并且乘法表下標(biāo)編號(hào)從1開始，比如2?×?3乘法表為
1 2 3
2 4 6
爺爺十分聰明，對(duì)于nm的乘法表惑惶，只要度度熊給出一個(gè)數(shù)k，爺爺就能立刻告訴度度熊乘法表中元素按照不減順序排列之后短纵，第k個(gè)元素是多少带污。你能重復(fù)這個(gè)游戲嗎？
輸入
輸入數(shù)據(jù)是三個(gè)整數(shù)：n, m, k (1≤n, m≤5105, 1≤k≤nm)香到。
樣例輸入
2 3 4
輸出
輸出nm乘法表按照不減順序排列的第k個(gè)數(shù)鱼冀。
樣例輸出
3
代碼：
import java.io.*;
import java.util.*;
public class Main {
public static long calSum(long k, long m, long n){
long sum = 0;
for(int i=1; i<=n; i++){
sum += (k>=m*i)?m:k/i;//求每一行小于等于k的個(gè)數(shù)报破，如果k>=m*i,這一行的個(gè)數(shù)為m,如果小于這一行的個(gè)數(shù)為k/i;
}
return sum;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
long n=sc.nextLong();
long m=sc.nextLong();
long k=sc.nextLong();
long left = 1;
long right =m*n;
long mid = right/2;
//使用二分查找
while(left<=right){
mid = (left+right)/2;
if(calSum(mid,m,n)<k){
left = mid+1;
}else{
right = mid-1;
}
}
System.out.println(left);
}
}
