Hướng dẫn giải của [Ninh Bình - TS10 - 2024] Bài 3: Số đặc biệt
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: ~(1 \leq M \leq 10^2; 1 \leq b \leq 10^3)~
Ta sẽ làm như những gì đề bài bảo: Duyệt tất cả các phần tử trong khoảng từ ~a~ đến ~b~ rồi tăng biến đếm nếu số ước của số đang xét đúng bằng ~3~. Sau đó, ta in ra biến đếm.
ĐPT: ~O~(~M \times b \times \sqrt{b}~)
Subtask 2: ~(1 \leq M \leq 10^3; 1 \leq b \leq 10^5)~
Đây là thuật toán cải tiến từ subtask ~1~.
Thay vì ta duyệt từng phần tử vào mỗi truy vấn, ta chuẩn bị trước mảng ~pfs_i~ với ý nghĩa là số các số có ước đúng bằng ~3~ trong khoảng từ ~1~ đến ~i~.
Kết quả của mỗi truy vấn chính là ~pfs_b - pfs_{a-1}~
ĐPT: ~O(b \times \sqrt{b})~
Subtask 3: Không có giới hạn gì thêm.
Nhận xét: Một số có đúng 3 ước khi và chỉ khi chúng tồn tại một ước ~x~ là số nguyên tố mà ~x^2~ đúng bằng số đó (bạn đọc tự chứng minh tính chất này).
Tương tự như subtask 2, ta cũng sẽ chuẩn bị trước mảng ~pfs_i~ với ý nghĩa là số các số có ước đúng bằng ~3~ trong khoảng từ ~1~ đến ~i~.
Gọi ~x~ là ~[\sqrt{b}]~, ~y~ là ~[\sqrt{a-1}]~.
Đáp số là ~pfs_x - pfs_y~.
ĐPT: ~O(b \times log(b))~
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int m;
struct Query {
int a, b;
} q[N];
namespace sub1 {
bool valid() {
bool ok = 0;
for (int i = 1; i <= m; i++) {
if (q[i].b > (int)1e3) return 0;
}
return m <= 100;
}
bool check(int x) {
int ret = 0;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0 and i * i != x) ret += 2;
if (i * i == x) ++ret;
}
return ret == 3;
}
void solve() {
for (int i = 1; i <= m; i++) {
int res = 0;
for (int j = q[i].a; j <= q[i].b; j++) {
res += check(j);
}
cout << res << "\n";
}
exit(0);
}
}
namespace sub2 {
bool valid() {
for (int i = 1; i <= m; i++) {
if (q[i].b > (int)1e5) return 0;
}
return m <= 1000;
}
bool check(int x) {
int ret = 0;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0 and i * i != x) ret += 2;
if (i * i == x) ++ret;
}
return ret == 3;
}
int pf[(int)1e5 + 1];
void solve() {
for (int i = 1; i <= (int)1e5; i++) {
pf[i] = pf[i - 1] + check(i);
}
for (int i = 1; i <= m; i++) {
cout << pf[q[i].b] - pf[q[i].a - 1] << "\n";
}
exit(0);
}
}
namespace subfull {
bool snt[(int)1e6 + 1];
void sieve() {
memset(snt, 1, sizeof snt);
snt[0] = snt[1] = 0;
for (int i = 2; i * i < N; i++) {
if (snt[i]) {
for (int j = i * i; j < N; j += i) {
snt[j] = 0;
}
}
}
}
int pf[(int)1e6 + 1];
void solve() {
sieve();
for (int i = 1; i <= (int)1e6; i++) {
pf[i] = pf[i - 1] + snt[i];
}
for (int i = 1; i <= m; i++) {
q[i].b = sqrt(q[i].b);
q[i].a = sqrt(q[i].a - 1);
cout << pf[q[i].b] - pf[q[i].a] << "\n";
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> q[i].a >> q[i].b;
}
if (sub1::valid()) sub1::solve();
if (sub2::valid()) sub2::solve();
subfull::solve();
return 0;
}
// <33
Bình luận