Hướng dẫn giải của Ước nguyên tố - LS
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 với mỗi số nguyên dương X (trong một danh sách các truy vấn), ta cần tìm ra ước nguyên tố lớn nhất của X. Nếu X không có ước nguyên tố nào (tức X = 1), kết quả là 0.
Các cách tiếp cận
Cách Phân tích thừa số nguyên tố (Sàng Eratosthenes nâng cao - SPF)
#include <bits/stdc++.h>
using namespace std;
const int MAX_A = 1000000;
vector<int> SPF(MAX_A + 1);
void sieve_spf() {
for (int i = 0; i <= MAX_A; i++) SPF[i] = i;
SPF[0] = SPF[1] = 1;
for (int i = 2; i * i <= MAX_A; i++) {
if (SPF[i] == i) {
for (int j = i * i; j <= MAX_A; j += i) {
if (SPF[j] == j) SPF[j] = i;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("uocnt.inp", "r", stdin);
freopen("uocnt.out", "w", stdout);
sieve_spf();
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
// Nếu x là số nguyên tố, SPF[x] == x
// Nếu x hợp số, SPF[x] là ước nguyên tố nhỏ nhất
// Để tìm ước nguyên tố lớn nhất, ta chỉ cần chia dần cho các ước nhỏ nhất
while (x > 1) {
int p = SPF[x];
x /= p;
if (x == 0 || x == 1) {
cout << p << "\n";
break;
}
if (SPF[x] == x) { // Phần còn lại là số nguyên tố
cout << x << "\n";
break;
}
}
}
return 0;
}
- Time Complexity: O(N log log N) để tiền xử lý + O(log X) cho mỗi truy vấn
- Space Complexity: O(MAX_A)
Phương pháp này xây dựng mảng SPF (Smallest Prime Factor) bằng sàng Eratosthenes. Với mỗi số X, ta chỉ cần lặp lại việc chia X cho ước nguyên tố nhỏ nhất của nó cho đến khi X chỉ còn lại một số nguyên tố. Số nguyên tố còn lại chính là ước nguyên tố lớn nhất của X ban đầu. Đây là phương pháp tối ưu nhất về thời gian truy vấn.
Cách Tối ưu Brute Force (Tìm ước từ lớn xuống)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000009;
vector<bool> nt(MAX, true);
void sang() {
nt[0] = nt[1] = false;
for (int i = 2; i * i < MAX; i++) {
if (nt[i]) {
for (int j = i * i; j < MAX; j += i) {
nt[j] = false;
}
}
}
}
long long uoc(long long n) {
ll ans = 0;
// Kiểm tra các ước từ 1 đến can(n)
for (ll i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (nt[i]) ans = max(ans, i);
if (i != n / i && nt[n / i]) ans = max(ans, n / i);
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("uocnt.inp", "r", stdin);
freopen("uocnt.out", "w", stdout);
sang();
int n;
cin >> n;
while (n--) {
ll x;
cin >> x;
cout << uoc(x) << "\n";
}
return 0;
}
- Time Complexity: O(N log log N) tiền xử lý + O(sqrt(X)) cho mỗi truy vấn
- Space Complexity: O(MAX)
Sử dụng sàng Eratosthenes để đánh dấu số nguyên tố. Với mỗi số X, ta duyệt các ước số từ 1 đến sqrt(X). Nếu i là ước và là số nguyên tố, ta cập nhật kết quả. Đồng thời kiểm tra ước kia là X/i. Phương pháp này chậm hơn do phải duyệt qua tất cả các ước, không chỉ các ước nguyên tố.
Cách Sàng Eratosthenes cơ bản ghi đè ước
#include <bits/stdc++.h>
#define ll long long
const ll MAXN = 1e6 + 1;
using namespace std;
bool prime[MAXN];
ll a[MAXN] = {};
void eratos() {
for (ll i = 1; i < MAXN; ++i) prime[i] = true;
prime[0] = prime[1] = false;
for (ll i = 2; i < MAXN; ++i) {
if (prime[i]) {
for (ll j = i; j < MAXN; j += i) {
prime[j] = false;
a[j] = i; // Ghi đè ước nguyên tố cuối cùng (lớn nhất)
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
freopen("uocnt.inp", "r", stdin);
freopen("uocnt.out", "w", stdout);
eratos();
ll n;
cin >> n;
while (n--) {
ll x;
cin >> x;
cout << a[x] << endl;
}
return 0;
}
- Time Complexity: O(N log log N)
- Space Complexity: O(MAXN)
Đây là biến thể của sàng Eratosthenes. Thay vì chỉ đánh dấu số nguyên tố, ta lưu lại ước nguyên tố. Tuy nhiên, vòng lặp j chạy với bước nhảy i (từ nhỏ đến lớn), nên a[j] sẽ được ghi đè bởi các ước nguyên tố lớn hơn xuất hiện sau này. Ví dụ: 6 được gán 2 trước, sau đó được gán 3. Cuối cùng a[6] = 3. Tuy nhiên, cách này chỉ đúng nếu i là ước nguyên tố lớn nhất của j. Trong các số hợp số, ước nguyên tố lớn nhất thường không phải là số được duyệt cuối cùng (ví dụ 10: i=2 gán a[10]=2, i=5 gán a[10]=5 -> Đúng). Nhưng với 12: i=2 gán a[12]=2, i=3 gán a[12]=3 -> Đúng. Có vẻ phương pháp này hoạt động đúng trong các ví dụ đơn giản nhưng không đảm bảo tính tổng quát nếu i không phải là ước.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N log log N) để tiền xử lý + O(log X) cho mỗi truy vấn | O(MAX_A) | Phân tích thừa số nguyên tố (Sàng Eratosthenes nâng cao - SPF) |
| 2 | O(N log log N) tiền xử lý + O(sqrt(X)) cho mỗi truy vấn | O(MAX) | Tối ưu Brute Force (Tìm ước từ lớn xuống) |
| 3 | O(N log log N) | O(MAXN) | Sàng Eratosthenes cơ bản ghi đè ước |
Bài học kinh nghiệm
- Phần lớn thời gian thực thi thuộc về tiền xử lý sàng số nguyên tố.
- Với mỗi truy vấn, ta nên xử lý thật nhanh (O(1) hoặc O(log X)) thay vì duyệt lại các ước (O(sqrt(X))).
- Việc sử dụng mảng SPF (Smallest Prime Factor) cho phép phân tích nhanh một số ra các thừa số nguyên tố.
Lỗi thường gặp
- Sử dụng kiểu dữ liệu quá nhỏ (ví dụ int) cho các số có thể lên tới 10^6 hoặc 10^9.
- Quên xử lý trường hợp X = 1 (kết quả là 0).
- Sai lầm trong việc xây dựng mảng ước nguyên tố lớn nhất bằng cách ghi đè đơn thuần mà không cần chia tách thừa số.
Bình luận