乘法表

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

样例

解析

直接通过长宽构造处整个乘法表矩阵最后排序输出在数据量比较大的时候势必会造成超时

所以，要想一种简单的方法，不需要去把整个矩阵全部构造出来

我们观察这个乘法表矩阵可以看到，从第二行开始每一行都是第一行的第i倍

可以利用这个特点去寻找在乘法表矩阵中的某个数在排好序后的序列中的位数

例如在一个4*4的矩阵中，如下

1 2 3 4

2 4 6 8

3 6 9 12

4 8 12 16

我们找寻8在排好序的数组中是第几位

可以用8除以i，因为行与行之间存在i倍关系。

i=1，8/1=8>=4 表示第一行全部的值都小于等于8

i=2，8/2=4>=4 表示第2行全部的值都小于等于8

i=3，8/3=2<=4 表示第3行2个值都小于等于8

i=4，8/4=2<=4 表示第4行2个值都小于等于8

所以8排在第4+4+2+2=12位 然后与所给的k进行比较即可

接下来就是我们所熟悉的二分法啦

代码

n, m, k = map(int, input().split())
low = 1
high = m * n
while low <= high:
    mid = (low + high) // 2
    num = 0  # 小于等于mid的数的个数
    for i in range(1, n+1):
        temp = mid // i  # 第i行中小于等于mid的数的个数
        if temp >= m:
            num += m  # 这一行全部小于等于mid
        else:
            num += temp  # 否则这一行有temp个
    if num < k:
        # 要找的值在mid的右边
        low = mid + 1
    else:
        # 左边
        high = mid - 1
print(low)