2016年百度实习生笔试之乘法表

度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为i*j，并且乘法表下标编号从1开始，比如2×3乘法表为 1 2 3 2 4 6 爷爷十分聪明，对于n*m的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？ 输入 输入数据是三个整数：n, m, k (1≤n, m≤5*105, 1≤k≤nm)。 样例输入 2 3 4 输出 输出n*m乘法表按照不减顺序排列的第k个数。 样例输出 3 时间限制 C/C++语言：1000MS其它语言：3000MS 内存限制 C/C++语言：65536KB其它语言：589824KB

首先分析这道题目，根据这个乘法表，比如乘法表 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 15 18

比如小于等于12的数的个数就是6+12/2+…12/3=16个，因此对于任意一个数，我们可以很容易分析在乘法表中小于等于该数的数的个数，这样我们就可以用二分查找了。

但是有一点要注意的是，这个里面的`数是有重复的，并不能直接用那种最原始的二分法查找，要有一些小的改进，比如上面这个表中小于等于12的数有16个，而要找第15个数，按照一般二分查找，又要在小于12的数里面找了，显然不对，可以加一个限制条件，比如小于等于12的数有16个，在判断小于等于11的数有多少个？若小于15，则这个数就是12。