Hướng dẫn giải của Nguyên tố _ 03.04_01
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 xử lý T test case. Với mỗi test case, cho một số nguyên dương M. Yêu cầu:
- In ra số ước của M (số lượng các ước số nguyên dương của M).
- In ra phân tích thừa số nguyên tố của M theo dạng: a1a2...*ak (các thừa số nguyên tố được liệt kê theo thứ tự tăng dần).
Ví dụ: M = 12 -> Số ước là 6 (1,2,3,4,6,12) và phân tích là 223.
Các cách tiếp cận
Cách Brute Force đếm ước và phân tích
void sub0() {
cin >> T;
for(int i = 1; i <= T; i++) {
cin >> M;
d_uoc = 0;
// Đếm ước bằng cách duyệt 1..M
for(int i = 1; i <= M; i++)
if(M % i == 0) d_uoc++;
cout << d_uoc << " ";
int k = 0;
int j = 2;
// Phân tích thừa số nguyên tố
while(M > 1) {
while(M % j == 0) {
luu[++k] = j;
M = M / j;
}
j++;
}
cout << luu[1];
for(int ii = 2; ii <= k; ii++) cout << '*' << luu[ii];
cout << '\n';
}
}
- Time Complexity: O(T * M)
- Space Complexity: O(1)
Phương pháp này dùng vòng lặp từ 1 đến M để đếm số ước, và lặp từ 2 để phân tích nguyên tố. Rất chậm, chỉ phù hợp với M nhỏ (< 10^5).
Cách Tối ưu đếm ước và Phân tích với Sieve
#include<bits/stdc++.h>
const int nmax = 1000005;
int d[nmax], T, A[nmax], luu[nmax], d_uoc, M, dem;
void sangnt(int k) {
int i, j;
d[1] = 1;
for(i = 2; i * i <= k; i++) {
if(d[i] == 0) {
j = i * i;
while(j <= k) {
d[j] = 1;
j += i;
}
}
}
}
void sol() {
cin >> T;
for(int i = 1; i <= T; i++) {
cin >> M;
d_uoc = 1;
int k = 0, uoc;
int j = 1;
if(d[M] == 0) {
// M là số nguyên tố
luu[++k] = M;
d_uoc *= 2;
} else {
while(M > 1) {
uoc = 0;
while(M % A[j] == 0) {
uoc++;
luu[++k] = A[j];
M = M / A[j];
}
d_uoc *= (uoc + 1);
j++;
}
}
cout << d_uoc << " ";
cout << luu[1];
// ... phần còn lại để in các thừa số khác
}
}
// Lưu ý: Code gốc có vẻ thiếu phần khai báo và dùng mảng A chưa rõ nguồn,
// nhưng logic là dùng Sieve để tối ưu vòng lặp phân tích.
- Time Complexity: O(N log log N + T * sqrt(M))
- Space Complexity: O(N)
Sử dụng Sieve of Eratosthenes để tạo mảng markings (d). Trong hàm sol, kiểm tra nhanh xem M có phải số nguyên tố không. Nếu không, thực hiện phân tích thừa số nguyên tố bằng cách lặp qua các số từ 2 (hoặc dùng mảng A chứa số nguyên tố đã tạo sẵn). Để đếm số ước, ta dùng công thức: nếu M = p1^a1 * p2^a2 ... thì số ước là (a1+1)(a2+1)*...
Cách Phân tích thừa số nguyên tố tối ưu (sqrt(M))
#include <bits/stdc++.h>
using namespace std;
void solve() {
int M;
cin >> M;
int original_M = M;
int count = 1; // Số ước
int k = 0; // Số lượng thừa số
// Đếm số ước và phân tích simultaneously
for (int i = 2; i * i <= M; i++) {
if (M % i == 0) {
int exp = 0;
while (M % i == 0) {
exp++;
luu[++k] = i; // Lưu thừa số
M /= i;
}
count *= (exp + 1);
}
}
// Nếu M còn lại > 1, nó là số nguyên tố
if (M > 1) {
count *= 2;
luu[++k] = M;
}
cout << count << " ";
for (int i = 1; i <= k; i++) {
if (i > 1) cout << "*";
cout << luu[i];
}
cout << "\n";
}
- Time Complexity: O(T * sqrt(M))
- Space Complexity: O(1) hoặc O(T) nếu lưu lại kết quả
Đây là cách tối ưu nhất cho bài toán này với ràng buộc M vừa phải (ví dụ 10^6). Thay vì dùng Sieve (tốn bộ nhớ và time precompute), ta chỉ cần lặp từ 2 đến căn bậc hai của M. Nếu M chia hết cho i, ta đếm số mũ (exp) và cập nhật số ước. Nếu duyệt hết vòng lặp mà M vẫn > 1, thì M đó là số nguyên tố cuối cùng. Phương pháp này cân bằng tốt giữa thời gian và bộ nhớ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(T * M) | O(1) | Brute Force đếm ước và phân tích |
| 2 | O(N log log N + T * sqrt(M)) | O(N) | Tối ưu đếm ước và Phân tích với Sieve |
| 3 | O(T * sqrt(M)) | O(1) hoặc O(T) nếu lưu lại kết quả | Phân tích thừa số nguyên tố tối ưu (sqrt(M)) |
Bài học kinh nghiệm
- Công thức tính số ước: Nếu N = p1^a1 * p2^a2 * ... * pk^ak thì số ước là (a1+1)(a2+1)...*(ak+1).
- Để tìm phân tích thừa số nguyên tố, chỉ cần lặp từ 2 đến căn bậc hai của số đó. Phần còn lại nếu > 1 chính là thừa số nguyên tố cuối cùng.
- Kiểm tra nhanh số nguyên tố (Sieve) có thể giúp tối ưu một bước, nhưng không bắt buộc nếu số lượng test case và giá trị M không quá lớn.
Lỗi thường gặp
- Quên xử lý trường hợp M = 1 (số ước là 1, không có thừa số nguyên tố).
- Lỗi vòng lặp: Vòng lặp
for (int i = 2; i*i <= M; i++)có thể bị lỗi nếu M thay đổi giá trị trong vòng lặp (phải dùng biến phụ hoặc tính trước giới hạn). Code mẫu trong Solution 1 dùngwhile(M > 1)nên tránh được lỗi này. - Xử lý in ấn: In sai định dạng (thiếu dấu '' hoặc thừa dấu '' ở đầu/cuối).
Bình luận
test có vấn đề rồi sốp ơi :)