推理流程:
首先以n=1000进行打表可以得到以下数据
#define For(i, a, b) for (int i = (a); i <= (b); i += 1)
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sz(x) (int)(x.size())
void db(int n) {
vector<int> a;
a.pb(0);
For(i, 1, n) {
a.pb(i * 2 - 2);
}
vector<int> pre(n + 1);
For (i, 1, n) {
pre[i] = pre[i - 1] + a[i];
}
vector<int> b;
For(i, 1, n) {
For(j, i + 1, n) {
// cout << i << ' ' << j << '\n';
b.pb(pre[j] - pre[i - 1]);
}
}
sort(all(b));
b.erase(unique(all(b)), b.end());
if (b.empty()) {
cout << '\n';
return;
}
For(i, 0, Sz(b) - 1) {
cout << b[i] << '\n';
}
cout << '\n';
}
2
6
10
12
14
... 数据很大 会明显发现1~1000种恰好少以4 8 16.. 二次幂 但是不包括2,其余偶数全部在,
那么大概guess出想要找到第k小,就可以去除4 8 16这些二的幂次 进行二分即可
Code
vector<i64> ans;
void init() {
for (i64 i = 2; i <= 63; i++) {
i128 x = 1LL << i;
ans.push_back(x);
}
}
std::ostream &operator<<(std::ostream &os, i128 n) {
if (n == 0) {
return os << 0;
}
std::string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
void Solve() {
i64 k;
cin >> k;
auto check = [&](i128 x) -> i128 {
if (x < 2) return 0;
i128 cnt = x / 2;
i128 it = upper_bound(all(ans), x) - ans.begin();
return cnt - it;
} ;
i128 l = 0, r = 4e18;
while (l < r) {
i128 mid = l + (r - l) / 2;
if (check(mid) >= k) {
r = mid;
} else {
l = mid + 1;
}
}
if (l & 1) {
l++;
}
cout << l << '\n';
}