Hướng dẫn giải của [VTT Q4 Contest 10] Bài 2: Cặp số [CAPSO]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm cặp ~(x, y)~ mà ~x^2~ và ~y^3~ cùng nằm trong ~[a, b]~ và lệch nhau không quá ~k~. Vì ~y^3 \le 10^{18}~ nên ~y \le 10^6~, ta chỉ cần duyệt ~y~ rồi đếm nhanh các ~x~.
Sub 1: Vét cạn — dùng khi ~b \le 1000~
Duyệt mọi ~x~, ~y~ rồi kiểm tra ba điều kiện. Nếu chỉ nộp sub này: đúng 10/10 test (vì bộ test chỉ có các test nhỏ nên vét cạn vẫn kịp thời gian).
Sub 2: Duyệt cặp — dùng khi ~b \le 10^6~
Với mỗi ~y~ hợp lệ, quét mọi ~x~ với ~x^2 \le b~. Độ phức tạp ~O(\sqrt{b} \cdot \sqrt[3]{b})~. Nếu chỉ nộp sub này: đúng 10/10 test.
Sub 3: Căn bậc hai nguyên — ~O(\sqrt[3]{b})~
Với mỗi ~y~, các ~x~ thỏa mãn khi ~x^2~ nằm trong ~[\max(a, y^3-k), \min(b, y^3+k)]~. Số ~x~ trong khoảng đó là hiệu hai căn bậc hai nguyên. Cần tính căn chính xác (chỉnh lại sau ~sqrtl~) và để ý ~y^3 + k~ tới ~2 \cdot 10^{18}~ vẫn nằm trong ~long long~. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Main đọc ~a, b, k~ rồi chọn sub theo ~b~: ~b \le 1000~ dùng sub1, ~b \le 10^6~ dùng sub2, còn lại sub3. Khi đi thi nên viết như vậy để sub sau sai vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, k;
// căn bậc hai nguyên: lớn nhất x với x*x <= v
ll isqrt_(ll v) {
if (v <= 0) return 0;
ll x = (ll)sqrtl((long double)v);
while (x * x > v) x--;
while ((x + 1) * (x + 1) <= v) x++;
return x;
}
// Sub 1: vét cạn mọi cặp (x, y) — dùng khi b <= 1000
void sub1() {
ll cnt = 0;
for (ll x = 1; x * x <= b; x++)
for (ll y = 1; y * y * y <= b; y++) {
ll p = x * x, q = y * y * y;
if (p >= a && q >= a && llabs(p - q) <= k) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: với mỗi y, quét mọi x — dùng khi b <= 10^6 (x <= 1000, y <= 100)
void sub2() {
ll cnt = 0;
for (ll y = 1; y * y * y <= b; y++) {
ll q = y * y * y;
if (q < a) continue;
for (ll x = 1; x * x <= b; x++) {
ll p = x * x;
if (p >= a && llabs(p - q) <= k) cnt++;
}
}
cout << cnt << "\n";
}
// Sub 3: với mỗi y (tới 10^6), đếm x bằng căn bậc hai nguyên theo khoảng [lo, hi]
void sub3() {
ll cnt = 0;
for (ll y = 1; y * y * y <= b; y++) {
ll q = y * y * y;
if (q < a) continue;
ll lo = max(a, q - k); // q - k không tràn vì k <= 10^18
ll hi = min(b, q + k); // q + k <= 2*10^18 vẫn nằm trong long long
if (lo > hi) continue;
cnt += isqrt_(hi) - isqrt_(lo - 1);
}
cout << cnt << "\n";
}
int main() {
freopen("CAPSO.INP", "r", stdin);
freopen("CAPSO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> a >> b >> k;
if (b <= 1000) sub1();
else if (b <= 1000000) sub2();
else sub3();
}
Bình luận