Hướng dẫn giải của [Beginner Free Contest 17] LAMP
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 đèn ~j~ bị lật đúng một lần với mỗi ước ~i~ của ~j~ (mọi ước đều không vượt quá ~N~). Bóng bật khi số ước của ~j~ là số lẻ, tức ~j~ là số chính phương. Đáp án là ~\lfloor \sqrt{N} \rfloor~.
Sub 1: Mô phỏng — ~O(N \log N)~, dùng khi ~N \le 5000~
Thực hiện đúng ~N~ thao tác: thao tác ~i~ lật các bóng ở bội của ~i~. Nếu chỉ nộp sub này: đúng 15/20 test (4 test lớn bị lỗi bộ nhớ, 1 test quá giờ khi chạy riêng).
Sub 2: Đếm số chính phương bằng vòng lặp — ~O(\sqrt{N})~, dùng khi ~N \le 10^{12}~
Đếm các ~k \ge 1~ thỏa ~k^2 \le N~. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 3: Căn bậc hai nguyên — ~O(1)~
Tính ~r = \lfloor \sqrt{N} \rfloor~ bằng ~sqrtl~ rồi hiệu chỉnh ~r~ sao cho ~r^2 \le N < (r+1)^2~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~N~, nếu ~N \le 5000~ gọi sub1, nếu ~N \le 10^{12}~ gọi sub2, ngược lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: N <= 5000. Mo phong truc tiep: thao tac i lat moi bong o vi tri chia het cho i.
void sub1() {
vector<char> on(N + 1, 0);
for (long long i = 1; i <= N; i++)
for (long long j = i; j <= N; j += i) on[j] ^= 1;
long long cnt = 0;
for (long long j = 1; j <= N; j++) cnt += on[j];
cout << cnt << "\n";
}
// Sub 2: N <= 10^12. Bong j bi lat mot lan voi moi uoc cua j, ma moi uoc cua j deu <= N.
// Bong j sang khi so uoc cua j le, tuc j la so chinh phuong. Dem k >= 1 voi k*k <= N (k <= 10^6).
void sub2() {
long long cnt = 0;
for (long long k = 1; k * k <= N; k++) cnt++;
cout << cnt << "\n";
}
// Sub 3: moi N. So chinh phuong <= N la floor(sqrt(N)), tinh chinh xac bang so nguyen.
void sub3() {
long long r = (long long)sqrtl((long double)N);
while (r * r > N) r--;
while ((r + 1) * (r + 1) <= N) r++;
cout << r << "\n";
}
int main() {
cin >> N;
if (N <= 5000) sub1();
else if (N <= 1000000000000LL) sub2();
else sub3();
return 0;
}
Bình luận