Hướng dẫn giải của LIST10: 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
Cho hai số nguyên dương ~L~ và ~R~. Hãy đếm và in ra các số trong đoạn ~[L, R]~ có đúng 4 ước, không kể 1 và chính nó.
Cách làm
Với mỗi số ~x~ trong đoạn ~[L, R]~, đếm số ~d~ thỏa mãn ~2 \le d < x~ và ~x~ chia hết cho ~d~. Nếu đếm được đúng 4 thì ~x~ là một đáp án.
- Bước 1: Đọc ~L~ và ~R~.
- Bước 2: Với mỗi ~x~ từ ~L~ đến ~R~, đếm số ước thực sự ~somuoc~.
- Bước 3: Nếu ~somuoc = 4~ thì lưu ~x~ vào mảng ~b~ và tăng ~dem~.
- Bước 4: In ~dem~ ở dòng đầu, các số trong ~b~ ở dòng thứ hai (đã theo thứ tự tăng dần vì ~x~ chạy từ nhỏ đến lớn).
Bẫy: không tính số 1 và chính số ~x~ là ước. Ví dụ ~6~ chỉ có 2 ước thực sự là 2 và 3, nên không thỏa mãn.
#include <bits/stdc++.h>
using namespace std;
int main() {
int L, R;
cin >> L >> R;
// b chứa các số có đúng 4 ước (không kể 1 và chính nó), dem là số lượng
int b[1005];
int dem = 0;
for (int x = L; x <= R; x++) {
// Đếm số ước thực sự của x, tức là các d từ 2 đến x-1 mà x chia hết cho d
int somuoc = 0;
for (int d = 2; d < x; d++) {
if (x % d == 0) {
somuoc++;
}
}
if (somuoc == 4) {
b[dem] = x;
dem++;
}
}
cout << dem << "\n";
for (int i = 0; i < dem; i++) {
cout << b[i] << " ";
}
cout << "\n";
return 0;
}
Bình luận