Hướng dẫn giải của SANGNT06: Số có 3 ước
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
Cho N (10 <= N <= 10^12), in ra số lượng và các số trong [1, N] có đúng 3 ước. Một số có đúng 3 ước khi và chỉ khi nó là bình phương của một số nguyên tố p, tức là p^2.
Sub 1: Đếm ước từng số — ~O(N \sqrt{N})~, dùng khi ~N \le 10^5~
Với mỗi x từ 1 đến N, đếm số ước bằng cách thử d đến căn bậc hai, rồi in các x có đúng 3 ước.
Nếu chỉ nộp sub này: đúng 10/20 test (các test N lớn bị quá giờ).
Sub 2: Liệt kê p^2 — ~O(\sqrt{N} \log \log \sqrt{N})~
Chỉ cần tìm các số nguyên tố p với p^2 <= N, tức p <= \sqrt{N} <= 10^6. Sàng các số đến \sqrt{N}, rồi mỗi số nguyên tố p cho một đáp án p^2. Bẫy: tính căn bậc hai nguyên cẩn thận (chỉnh lại sau khi lấy căn) và dùng long long.
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 <= 10^5 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
// So co dung 3 uoc <=> so do la p^2 voi p la so nguyen to.
// Sub 1: thu tung so x trong [1, N], dem uoc bang cach thu chia — dung khi N <= 100000
void sub1() {
vector<long long> res;
for (long long x = 1; x <= N; x++) {
long long cnt = 0;
for (long long d = 1; d * d <= x; d++) {
if (x % d == 0) {
cnt++; // d la uoc
if (d != x / d) cnt++; // x/d la uoc khac
}
}
if (cnt == 3) res.push_back(x);
}
cout << res.size() << "\n";
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 < res.size() ? " " : "\n");
}
// Sub 2: sang cac so nguyen to p <= sqrt(N), roi in p^2 — dung cho N lon
void sub2() {
long long lim = (long long)sqrtl((long double)N);
while (lim * lim > N) lim--;
while ((lim + 1) * (lim + 1) <= N) lim++;
vector<bool> comp(lim + 2, false);
vector<long long> res;
for (long long p = 2; p <= lim; p++) {
if (comp[p]) continue;
res.push_back(p * p);
for (long long j = p * p; j <= lim; j += p) comp[j] = true;
}
cout << res.size() << "\n";
for (size_t i = 0; i < res.size(); i++)
cout << res[i] << (i + 1 < res.size() ? " " : "\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 100000) sub1();
else sub2();
return 0;
}
Bình luận