Hướng dẫn giải của Đèn nháy (TS 10 chuyên Ninh Bình 2022)
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
Bóng thứ ~i~ bị đảo đúng một lần với mỗi ước của ~i~ (các ước đều không vượt ~n~ vì ~i \le n~). Bóng bật khi và chỉ khi ~i~ có số ước lẻ, tức ~i~ là số chính phương. Cần đếm số chính phương trong ~[p; q]~.
Sub 1: Duyệt từng bóng — ~O(q - p)~, dùng khi ~q - p \le 10^6~
Kiểm tra từng ~i~ trong ~[p; q]~ có phải chính phương không. Nếu chỉ nộp sub này: đúng 23/50 test.
Sub 2: Công thức căn bậc hai — ~O(1)~ (tính căn nguyên)
Số chính phương trong ~[p; q]~ bằng ~\lfloor \sqrt{q} \rfloor - \lfloor \sqrt{p-1} \rfloor~. Căn được tính bằng ~sqrtl~ rồi chỉnh lại để tránh sai số. Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Nếu ~q - p \le 10^6~ dùng sub 1, còn lại dùng sub 2. Khi đi thi nên viết như vậy: 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 P, Q, N; // doan [P; Q] (Q <= N)
// can bac hai nguyen (lam tron xuong), chinh sai so cho chac chan
long long isq(long long x) {
long long r = (long long)sqrtl((long double)x);
while (r * r > x) r--;
while ((r + 1) * (r + 1) <= x) r++;
return r;
}
// Y tuong: bong den thu i tat/bat theo so uoc cua i, ma i co so uoc le khi va chi khi i la so chinh phuong.
// Nen dem so chinh phuong trong [P; Q].
// Sub 1: duyet tung i trong [P; Q] va kiem tra chinh phuong — dung khi Q - P nho
void sub1() {
long long cnt = 0;
for (long long i = P; i <= Q; i++)
if (isq(i) * isq(i) == i) cnt++;
cout << cnt << "\n";
}
// Sub 2: cong thuc — so chinh phuong trong [P; Q] = isq(Q) - isq(P - 1)
void sub2() {
cout << isq(Q) - isq(P - 1) << "\n";
}
int main() {
freopen("DN.INP", "r", stdin);
freopen("DN.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> P >> Q >> N;
if (Q - P <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận