百度16年编程题-乘法表

题目描述

度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为ij，并且乘法表下标编号从1开始，比如2 × 3乘法表为
1 2 3
2 4 6
爷爷十分聪明，对于nm的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLong()){
            long n = scan.nextLong(); //行
            long m = scan.nextLong(); //列
            long k =scan.nextLong();
            
            long left = 1;
            long right =m*n;
            long mid = right/2;
            while (left <= right){
                mid = (left+right)/2;
                long count = 0;
  //这个题目的关键是二分查找法，首先确定中间值的位置，
//如果中间值位置大于等于要查找的K的位置，则把右边位置放到中间值；否则左边位置为中间值
                for(int i=1;i<=n;i++){
                    long tmp = (mid >= i*m)?m:mid/i;
                    count +=tmp;
                }
                if(count < k){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            System.out.println(left);
        }
    }
}