Hướng dẫn giải của [2026-2027] Đề minh họa THPT Phú Thọ - Câu 3
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Yêu cầu: tìm ~n~ nhỏ nhất để sau quá trình đảo trạng thái có đúng ~k~ bóng còn sáng.
Sub 1: Duyệt tăng n — ~O(k)~, dùng khi ~k \le 10^6~
Bóng ~j~ bị đảo đúng một lần cho mỗi ước của ~j~ nằm trong ~[1, n]~, nên bóng ~j~ tắt khi ~j~ là số chính phương. Số bóng sáng là ~n - \lfloor \sqrt{n} \rfloor~. Tăng ~n~ từng bước cho đến khi đạt ~k~.
Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Tìm nhị phân — ~O(\log^2 k)~
Hàm ~n - \lfloor \sqrt{n} \rfloor~ không giảm và tăng từng bước 0 hoặc 1 nên tìm nhị phân được ~n~ nhỏ nhất. Căn bậc hai tính chính xác bằng cách hiệu chỉnh số nguyên. Giới hạn trên ~2k+2~ là đủ.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Mỗi truy vấn: nếu ~k \le 10^6~ gọi sub 1, còn lại gọi sub 2. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long K; // số bóng đèn còn sáng cần đạt
// Căn bậc hai nguyên của n
long long isqrtll(long long n) {
long long s = (long long)sqrtl((long double)n);
while (s * s > n) s--;
while ((s + 1) * (s + 1) <= n) s++;
return s;
}
// Với n bóng: bóng j chỉ bị đảo một số lần bằng số ước của j (j <= n),
// nên bóng j tắt khi j là số chính phương. Số bóng còn sáng = n - floor(sqrt(n)).
long long lit(long long n) { return n - isqrtll(n); }
// Sub 1: tăng n từng bước, dùng khi K <= 10^6
void sub1() {
long long n = 1;
while (lit(n) < K) n++;
cout << n << "\n";
}
// Sub 2: tìm nhị phân trên n (hàm lit không giảm), dùng cho K lớn
void sub2() {
long long lo = 1, hi = 2 * K + 2;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (lit(mid) >= K) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> K;
if (K <= 1000000) sub1();
else sub2();
}
return 0;
}
Bình luận