Hướng dẫn giải của Các số có 4 ướ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
Đếm các số trong đoạn ~[L,R]~ có đúng 4 ước không tính 1 và chính nó, tức là tổng cộng 6 ước, và in các số đó.
Sub 1: Thử chia từng số — ~O(R\sqrt{R})~, dùng khi ~R \le 10000~
Với mỗi số x trong đoạn, đếm ước d với ~d \le \sqrt{x}~ (mỗi cặp d, x/d tính 2 ước). Nếu tổng số ước là 6 thì ghi nhận x.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng số ước — ~O(R\log R)~
Với mỗi d từ 1 đến R, cộng 1 vào số ước của mọi bội của d. Sau đó lấy các x trong đoạn có đúng 6 ước.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc L, R. Nếu R \le 10000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int L, R;
vector<int> ans; // cac so co dung 4 uoc trong [L, R]
// Sub 1: voi moi so, thu cac uoc d <= sqrt(x). Dung khi R <= 10000
void sub1() {
for (int x = L; x <= R; x++) {
int c = 0;
for (int d = 1; d * d <= x; d++)
if (x % d == 0) {
c++;
if (d * d != x) c++;
}
if (c == 6) ans.push_back(x);
}
}
// Sub 2: sang so uoc, cnt[x] = so uoc cua x (moi d chia het cho cac boi cua no). O(R log R)
void sub2() {
vector<int> cnt(R + 1, 0);
for (int d = 1; d <= R; d++)
for (int m = d; m <= R; m += d) cnt[m]++;
for (int x = L; x <= R; x++)
if (cnt[x] == 6) ans.push_back(x);
}
int main() {
cin >> L >> R;
if (R <= 10000) sub1();
else sub2();
cout << ans.size() << "\n";
for (size_t i = 0; i < ans.size(); i++) {
if (i) cout << " ";
cout << ans[i];
}
cout << "\n";
return 0;
}
Bình luận