Hướng dẫn giải của [VT Thiếu nhi] BÀI 24: SO3UOC
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
Số có đúng ba ước là bình phương của một số nguyên tố, tức là ~p^2~. Cần đếm số dạng này trong đoạn ~[a, b]~, với ~b \le 10^9~.
Sub 1: Vét cạn — ~O(b^2)~, dùng khi ~b \le 1000~
Với mỗi ~x~ trong ~[a, b]~, đếm ước bằng cách thử mọi ~d \le x~ và kiểm tra có đúng ba ước không. Bộ test chấm đều có ~b~ lớn nên sub này không ăn được test nào (0/20), nhưng đúng với ví dụ trong đề (~1~ ~16~ cho ~2~) và là cách chắc chắn cho dữ liệu nhỏ.
Sub 2: Duyệt căn nguyên tố — ~O(\sqrt{b} \cdot \sqrt[4]{b})~
Đếm ~r~ nguyên tố sao cho ~a \le r^2 \le b~. Vì ~b \le 10^9~ nên ~r \le 31623~, kiểm tra nguyên tố bằng chia thử đến căn của ~r~. Đây là lời giải đầy đủ đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~a, b~. Nếu ~b \le 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long a, b;
// So co dung 3 uoc la p^2 voi p la so nguyen to (vi du 4, 9, 25, 49).
bool isPrime(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can. Voi moi x trong [a,b], dem uoc bang cach thu tat ca d tu 1 den x.
// Dung khi b <= 1000.
void sub1() {
long long cnt = 0;
for (long long x = a; x <= b; x++) {
int ud = 0;
for (long long d = 1; d <= x; d++)
if (x % d == 0) ud++;
if (ud == 3) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: x co 3 uoc <=> x = r^2 voi r nguyen to. Duyet r tu 2 den sqrt(b) (<= 31623),
// dem r sao cho a <= r*r <= b va r la so nguyen to.
void sub2() {
long long cnt = 0;
for (long long r = 2; r * r <= b; r++)
if (r * r >= a && isPrime(r)) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("SO3UOC.INP", "r", stdin);
freopen("SO3UOC.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> a >> b;
if (b <= 1000) sub1();
else sub2();
return 0;
}
Bình luận