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。