Hướng dẫn giải của Tích các số nguyên tố
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm tất cả các số nguyên trong đoạn [X, Y] có thể được tạo thành bằng cách nhân các số nguyên tố từ một tập hợp cho trước. Số 1 được coi là hợp lệ (tương ứng với tích rỗng). Các số nguyên tố có thể được sử dụng nhiều lần, và kết quả cần được in ra theo thứ tự tăng dần, phân tách bằng dấu phẩy.
Các cách tiếp cận
Cách Backtracking (DFS) cơ bản
#include <iostream>
#include <set>
#include <vector>
using namespace std;
long long X, Y;
int n;
vector<int> primes;
set<long long> results;
void backtrack(int idx, long long currentVal) {
if (currentVal > Y) return;
if (currentVal >= X) results.insert(currentVal);
for (int i = idx; i < primes.size(); i++) {
if (currentVal > Y / primes[i]) continue; // Tràn số
backtrack(i, currentVal * primes[i]);
}
}
int main() {
while (cin >> n && n != 0) {
primes.resize(n);
for (int i = 0; i < n; i++) cin >> primes[i];
cin >> X >> Y;
results.clear();
results.insert(1); // Luôn có số 1
backtrack(0, 1);
if (results.empty()) {
cout << "none" << endl;
} else {
bool first = true;
for (auto val : results) {
if (val >= X && val <= Y) {
if (!first) cout << ",";
cout << val;
first = false;
}
}
cout << endl;
}
}
return 0;
}
- Time Complexity: O(S * N) hoặc O(Number of products)
- Space Complexity: O(Number of products)
Phương pháp này sử dụng đệ quy (backtracking) để duyệt qua tất cả các cách kết hợp số nguyên tố. Hàm backtrack(idx, currentVal) thử nhân currentVal với các số nguyên tố từ chỉ số idx trở đi. Điều kiện dừng là khi tích vượt quá Y. Đây là cách tiếp cận trực quan nhất, tạo ra các số theo thứ tự (không cần sort) nếu các số nguyên tố đầu vào được sắp xếp và ta duyệt từ trái sang phải.
Cách Quay lui với kiểm soát thứ tự và loại bỏ trùng lặp
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
long long X, Y;
vector<int> primes;
vector<long long> ans;
void solve(int idx, long long val) {
if (val >= X && val <= Y) {
ans.push_back(val);
}
if (val > Y) return;
for (int i = idx; i < primes.size(); ++i) {
if (val > Y / primes[i]) continue;
solve(i, val * primes[i]);
}
}
int main() {
int n;
while (cin >> n && n != 0) {
primes.resize(n);
for (int i = 0; i < n; ++i) cin >> primes[i];
cin >> X >> Y;
ans.clear();
ans.push_back(1); // Luon co 1
solve(0, 1);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
bool found = false;
for (long long v : ans) {
if (v >= X && v <= Y) {
if (found) cout << ",";
cout << v;
found = true;
}
}
if (!found) cout << "none";
cout << "\n";
}
return 0;
}
- Time Complexity: O(Number of products * log Number of products)
- Space Complexity: O(Number of products)
Đây là biến thể của Backtracking. Thay vì dùng set để tự động loại trùng và sắp xếp, ta dùng vector và thực hiện sort + loại bỏ trùng lặp (unique) sau khi sinh xong. Phương pháp này có thể hiệu quả hơn một chút về mặt bộ nhớ và tốc độ chép dữ liệu so với set, nhưng tổng độ phức tạp vẫn phụ thuộc vào số lượng tích sinh ra.
Cách BFS (Breadth-First Search) / Duyệt theo cấp số nhân
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
vector<int> primes(n);
for (int i = 0; i < n; i++) cin >> primes[i];
long long X, Y;
cin >> X >> Y;
set<long long> s;
s.insert(1);
queue<long long> q;
q.push(1);
while (!q.empty()) {
long long curr = q.front();
q.pop();
for (int p : primes) {
// Kiểm tra tràn số trước khi nhân
if (curr > Y / p) continue;
long long nextVal = curr * p;
if (nextVal <= Y) {
if (s.find(nextVal) == s.end()) {
s.insert(nextVal);
q.push(nextVal);
}
}
}
}
vector<long long> res(s.begin(), s.end());
bool found = false;
for (long long v : res) {
if (v >= X && v <= Y) {
if (found) cout << ",";
cout << v;
found = true;
}
}
if (!found) cout << "none";
cout << "\n";
}
return 0;
}
- Time Complexity: O(Number of products * N)
- Space Complexity: O(Number of products)
Sử dụng thuật toán BFS để duyệt. Bắt đầu từ 1, ta nhân với từng số nguyên tố để tạo ra các số mới và đưa vào hàng đợi. Sử dụng set để đảm bảo mỗi số chỉ được xử lý một lần. Phương pháp này tránh được nguy cơ tràn stack của đệ quy (dù trong bài này số lượng tích không lớn) và có thứ tự sinh ra rõ ràng.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(S * N) hoặc O(Number of products) | O(Number of products) | Backtracking (DFS) cơ bản |
| 2 | O(Number of products * log Number of products) | O(Number of products) | Quay lui với kiểm soát thứ tự và loại bỏ trùng lặp |
| 3 | O(Number of products * N) | O(Number of products) | BFS (Breadth-First Search) / Duyệt theo cấp số nhân |
Bài học kinh nghiệm
- Bài toán này là bài toán sinh các số có dạng tích các thừa số nguyên tố. Số lượng các tích này phát triển theo hàm mũ, nhưng do giới hạn Y ≤ 10^9, số lượng tích thực tế không quá lớn (ví dụ với số nguyên tố nhỏ, số tích ≤ 10^9 là khoảng 4479).
- Cần phải xử lý tràn số nguyên (integer overflow) cẩn thận. Thay vì kiểm tra
a * b > Y, nên kiểm traa > Y / b(nếu Y chia hết cho b) hoặca > Y / b(sử dụng số học số nguyên). - Số 1 luôn phải được thêm vào danh sách kết quả ban đầu.
Lỗi thường gặp
- Không kiểm tra tràn số khi nhân, dẫn đến lỗi logic (ví dụ:
curr * pvượt quá giới hạn củalong longhoặc biến thành số âm, không vượt qua được điều kiện> Y). - Sử dụng mảng cố định quá nhỏ cho kết quả (nếu dùng mảng thay vì vector/set). Số lượng tích có thể lên tới hàng chục nghìn.
- In thừa dấu phẩy ở cuối danh sách hoặc thiếu dấu phẩy giữa các số.
Bình luận