Hướng dẫn giải của Số có ước nguyên dương (đề Bình Định 2021)
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à p^2 với p nguyên tố.
Sub 1: Vét cạn, ~O(N \log N)~ (N ≤ 10^6)
Sàng số ước của mọi n ≤ N, đếm n có đúng 3 ước. Đúng 20/25 test.
Sub 2: Đếm số nguyên tố, ~O(10^6 \log \log 10^6)~
Sàng các số nguyên tố đến 10^6, đếm p có p^2 ≤ N. Đúng 25/25 test.
Chương trình hoàn chỉnh
main: N ≤ 10^6 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Mot so co dung 3 uoc duong khi va chi khi no co dang p^2 voi p la so nguyen to.
// Sub 1: vet can. Voi moi n tu 1 den N, dem so uoc cua n (sang kieu "moi d chia het boi so n")
// roi dem cac n co dung 3 uoc. Dung khi N <= 10^6.
void sub1() {
vector<int> d(N + 1, 0);
for (long long i = 1; i <= N; i++)
for (long long j = i; j <= N; j += i) d[j]++;
long long cnt = 0;
for (long long n = 1; n <= N; n++)
if (d[n] == 3) cnt++;
cout << cnt << "\n";
}
// Sub 2: so can dung 3 uoc la p^2 voi p nguyen to va p^2 <= N. Sang cac so nguyen to den 10^6
// (vi p <= sqrt(10^12) = 10^6), roi dem cac p co p*p <= N.
void sub2() {
const int M = 1000000;
vector<bool> comp(M + 1, false);
for (int i = 2; (long long)i * i <= M; i++)
if (!comp[i])
for (int j = i * i; j <= M; j += i) comp[j] = true;
long long cnt = 0;
for (int p = 2; p <= M; p++)
if (!comp[p] && (long long)p * p <= N) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("bauoc.inp", "r", stdin);
freopen("bauoc.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận