乘法表（百度2016实习生真题）

题目描述
度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为ij，并且乘法表下标编号从1开始，比如2 × 3乘法表为
1 2 3
2 4 6
爷爷十分聪明，对于nm的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？
输入
输入数据是三个整数：n, m, k (1≤n, m≤5105, 1≤k≤nm)。
样例输入
2 3 4
输出
输出nm乘法表按照不减顺序排列的第k个数。
样例输出
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的个数，如果k>=m*i,这一行的个数为m,如果小于这一行的个数为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);
    }
        
        
}