Register | Login

Solutions of Multiplication table

Select solution language All Tiếng Việt English Other

Write solution here.

---

Sherwin    Created at    1 likes

Ý tưởng: với mỗi mid thì ta tìm xem có bao nhiêu số trong bảng nhỏ hơn mid, sau đó đem so sánh với k Khai báo l = 1, r = n*m; Để tìm số lượng số nhỏ hơn mid, với **mỗi dòng** i (1 <= i <= n) tăng biến đêm lên min(mid/i, **số cột**) **Ở đây mình chạy biến i theo số dòng nhưng cũng có thể chạy theo m tùy theo cách bạn nghĩ** ĐPT: O(n * log(n*m)) Code mẫu: #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n, m, k; cin >> n >> m >> k; long long l = 1, r = n*m; while (r >= l){ long long mid = (l + r)/2, de = 0; for (int i = 1; i <= n; ++i) de += min(mid/i, m); if (de < k) l = mid + 1; else r = mid - 1; } cout << l; }