題目#
給你 \(n\) 和 \(k\)，請求出 \(n\times n\) 乘法表中第 \(k\) 小的數字。
解題思路#
直接建表排序太慢了，時間複雜度高達 \(O(n^2 \times log(n))\)，我們需要一個更快的方法。題目是詢問第 \(k\) 小的數字，答案範圍又很大，有機會可以用「第 \(k\) 大二分搜」解決（雖然這邊是第 \(k\) 小）。
對於每一個答案，使用雙指針，一個設為 \(1\)，另外一個設為 \(n\)。當第一個指針增加的時候，第二個指針要一直減一，直到兩個指針乘積 \(\leq\) 答案。第二個指針所停留的數字就是在其中一個數字為第一個指針的時候，能讓兩指針相乘不超過答案的數字個數。將他們相加就能得到乘法表中有多少個數小於等於答案。
常見錯誤#
- 記得開 long long（ \(k\) 和答案最大都高達 \(10^{10}\) ）
完整程式碼#
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, k;
cin >> n >> k;
long long l = 0, r = 1e10;
while (l < r) {
long long m = (l + r) / 2;
long long cnt = 0;
long long p1 = n;
for (int p2 = 1; p2 <= n; p2++) {
while (p1 * p2 > m){
p1--;
}
cnt += p1;
}
if (cnt < k) {
l = m + 1;
}
else{
r = m;
}
}
cout << l << "\n";
}
