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

朱雀 2022-11-15 05:51 182阅读 0赞

**题目描述：**

度度熊和爷爷在玩一个乘法表游戏。乘法表的第i行第j列位置的元素为`i*j`，并且乘法表下标编号从1开始，比如`2 × 3`乘法表为

1 2 3
    2 4 6

爷爷十分聪明，对于n\*m的乘法表，只要度度熊给出一个数k，爷爷就能立刻告诉度度熊乘法表中元素按照不减顺序排列之后，第k个元素是多少。你能重复这个游戏吗？

--------------------

**解题思路:**

使用二分查找

--------------------

**代码：**

Python代码：

def num(m, n, mid): #找出每行小于mid的个数
        sum = 0
        for i in range(1, m+1):
            if i*n < mid:
                sum += n
            else:
                sum += mid//i
        return sum
    
    while True:
        n, m, k = map(int, input().split())  # 赛码网数据输入方法
        min = 1
        max = n*m
        while min <= max:
            mid = (min+max)//2
            sum = num(m, n, mid)
            if sum >= k:
                max = mid - 1
            else:
                min = mid + 1
        print(min)

--------------------

问题代码：

while True:
        n, m, k = (int(i) for i in input().split())
        if m == 0:
            print((list(range(1, n+1)))[k-1])
            break
        result = []
        for i in range(1, n+1):
            for j in range(1, m+1):
                result.append(i * j)
        arry = list(sorted(result))
        print(arry)
        print(arry[k-1])

--------------------

**题目来源：**

[https://exercise.acmcoder.com/online/online\_judge\_ques?ques\_id=3819&konwledgeId=40][https_exercise.acmcoder.com_online_online_judge_ques_ques_id_3819_konwledgeId_40]

[https_exercise.acmcoder.com_online_online_judge_ques_ques_id_3819_konwledgeId_40]: https://exercise.acmcoder.com/online/online_judge_ques?ques_id=3819&konwledgeId=40