Chúng ta cần tìm giá trị \(X\) đứng tại vị trí chính giữa sau khi sắp xếp, tức là có đúng \((N^2+1)/2\) phần tử trong bảng nhân \(\le X\).

Ta thực hiện Tìm kiếm nhị phân trên không gian đáp án của \(X\) trong khoảng \([1, N^2]\):

• Đặt lo = 1, hi = N * N.
• Với mỗi bước, lấy mid = lo + (hi - lo) / 2.
• Hàm kiểm tra: đếm xem có bao nhiêu phần tử trong bảng nhân có giá trị \(\le mid\).
• Ở mỗi hàng \(i\) (\(1 \le i \le N\)), các số có giá trị là \(i \times 1, i \times 2, \dots, i \times N\).
  • Số lượng số trong hàng \(i\) thỏa mãn \(i \times j \le mid\) là \(\min(N, \lfloor mid / i \rfloor)\).
  • Vậy tổng số lượng phần tử \(\le mid\) trong toàn bộ bảng nhân là: \[Count = \sum_{i=1}^N \min\left(N, \left\lfloor \frac{mid}{i} \right\rfloor\right)\]
  • Độ phức tạp để đếm là \(O(N)\) bằng cách duyệt qua từng hàng.
• Nếu \(Count \ge (N^2 + 1) / 2\): giá trị \(mid\) có thể làm số trung vị hoặc lớn hơn, ta thử giảm nghiệm gán hi = mid.
• Ngược lại, nếu \(Count < (N^2 + 1) / 2\): giá trị \(mid\) quá nhỏ, ta tăng nghiệm gán lo = mid + 1.

Độ phức tạp: \(O(N \log(N^2))\). Với \(N = 10^6\), số bước lặp khoảng \(40\), tổng số phép tính \(\approx 4 \times 10^7\) hoàn toàn chạy trong giới hạn 1.0 giây của C++.

#include <iostream>
#include <algorithm>

using namespace std;

long long countLessEqual(long long n, long long val) {
    long long count = 0;
    for (long long i = 1; i <= n; ++i) {
        count += min(n, val / i);
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n;
    if (!(cin >> n)) return 0;

    long long target = (n * n + 1) / 2;
    long long lo = 1, hi = n * n;
    long long ans = hi;

    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (countLessEqual(n, mid) >= target) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}