Hướng dẫn giải của [Ninh Bình - TS10 - 2022] Bài 4: Đèn nháy
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.
Tác giả:
Subtask ~1~: ~n \le 3000~
Ở subtask này, ta sẽ làm đúng như những gì đề bài bảo.
Với mỗi lần thay đổi trạng thái thứ ~i~, ta sẽ duyệt lại từ ~1~ đến ~n~ để kiểm tra xem liệu vị trí đó có chia hết cho ~i~ hay không.
ĐPT: ~O~(~n^2~).
Subtask ~2~: ~10^4 \le n \le 10^5~
Đây là subtask cải tiến từ subtask ~1~.
Với mỗi lần thay đổi trạng thái thứ ~i~, thay vì ta duyệt hết mọi phần tử trong khoảng từ ~1~ đến ~n~, ta sẽ bắt đầu duyệt từ vị trí thứ ~i~, và tiến hành thay đổi mỗi khi vị trí mới hơn vị trí trước đó ~i~ phần tử.
ĐPT: ~O~(~n \times log(n)~)
Bạn đọc có thể xem chứng minh độ phức tạp ở đây
Subtask ~3~: ~10^7 \le n \le 10^{18}~
Nhận xét: Một đèn ở vị trí ~x~ bị đổi trạng thái nếu ~i~ là ước của ~x~.
Do đó, số lần đảo trạng thái của ~x~ chính là số ước của ~x~.
Để đèn lồng bật sau khi thực hiện thao tác, thì số ước của ~x~ phải là số lẻ. Mà một số có số ước lẻ khi và chỉ khi đó là số chính phương.
(Bạn đọc tự chứng minh tính chất này).
=> Số bóng đèn bật trong khoảng từ ~1~ đến ~n~ chính là phần nguyên của ~\sqrt{n}~.
=> Đáp số bài toán là ~[\sqrt{q}]~ - ~[\sqrt{p - 1}]~
ĐPT: ~O~(~log(n)~) do phụ thuộc vào độ phức tạp của hàm std::sqrt()
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int l, r, n;
namespace sub1 {
bool valid() {
return n <= 3000;
}
bool a[3001];
void solve() {
for (int i = 1; i <= n; i++) {
// lần thay đổi trạng thái
for (int j = 1; j <= n; j++) {
// vị trí đèn đang xét
if (j % i == 0) {
a[j] ^= 1;
}
}
}
int res = 0;
for (int i = l; i <= r; i++) {
if (a[i] == 1) {
++res;
}
}
cout << res;
exit(0);
}
}
namespace sub2 {
bool valid() {
return n <= (int)1e5;
}
bool a[(int)1e5 + 1];
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
if (j % i == 0) {
a[j] ^= 1;
}
}
}
int res = 0;
for (int i = l; i <= r; i++) {
if (a[i] == 1) {
++res;
}
}
cout << res;
exit(0);
}
}
namespace subfull {
void solve() {
int cntr = sqrt(r);
int cntl = sqrt(l - 1);
cout << cntr - cntl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> l >> r >> n;
if (sub1::valid()) sub1::solve();
if (sub2::valid()) sub2::solve();
subfull::solve();
return 0;
}
// <33
Bình luận