Tìm số thứ k trong ma trận m*n

[An_Nguyen (An Nguyễn)]

Mọi người cho em hỏi bài này với ạ:

Cho 1 bảng kích thước N dòng M cột, chỉ số được đánh từ 1. Ô ở dòng i, cột j là (i,j) sẽ có giá trị là i∗j. Hỏi sau khi sắp xếp N∗M số trong bảng theo thứ tự không giảm, thì số thứ K là số nào?

Input

Trên một dòng gồm 3 số nguyên
N,M,K(N,M≤5∗10^5,K≤N∗M).

Output

In ra số nguyên duy nhất là giá trị của số thứ K
VD:
input:

3 4 8

output:

6

[sbgssol (lee)]

Bạn đang ko rõ đề bài hay sao ?

[An_Nguyen (An Nguyễn)]

e hiểu đề nhưng e muốn mọi người giúp e về thuật toán. Vì e dùng mảng 2 chiều để lưu giá trị thì nó bị tràn :(((

[rogp10]

Tích sẽ “tăng dần” theo đường chéo phụ. Dự là O(sqrt(K))

p/s: Cauchy cho ta thấy số lớn nhất trong đường chéo phụ là giao điểm với đường chéo chính hoặc là hai bên của nó.

[Grevyalres_X (Pzanitor)]

đơn giản thì:
với mỗi số X tìm được số cặp (i,j) sao cho i * j <= X, tạm gọi số lượng cặp (i,j) này là F(X).
-> tìm số X sao cho F(X) <= K <= F(X+1) bằng chặt nhị phân.