Hiểu bài toán

Bài toán yêu cầu phân tích một số nguyên dương n (1 ≤ n ≤ 10^12) thành thừa số nguyên tố. Đầu tiên, in ra số lượng các thừa số nguyên tố distint (khác nhau). Sau đó, in ra từng thừa số nguyên tố cùng với số mũ (số lần nó xuất hiện) trong phân tích của n. Ví dụ, nếu n = 12 = 2^2 * 3, đầu ra là: 2 2 2 3 1

Các cách tiếp cận

Cách Brute Force với tối ưu hóa cơ bản

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, nt[1000011], cnt;
ll check_nt(ll n){
    if(n<2) return 0;
    for(ll i=2; i<=sqrt(n); i++) {
        if(n%i==0) return 0;
    }
    return 1;
}
ll demntkn(ll n){
    ll res=0;
    for(ll i=2; i<=sqrt(n); i++){
        if(n%i==0){
            res++;
            while(n%i==0) n/=i;
        }
    }
   if(n!=1) res++;
   return res;
}
int main(){
    cin>>n;
    ll m=n;
    cout<<demntkn(n)<<endl;
    for(ll i=2; i<=sqrt(m); i++){
        if(check_nt(i) && n%i==0){
            cnt=0;
            while(n%i==0){
                cnt++;
                n=n/i;
            }
            cout<<i<<" "<<cnt<<endl;
        }
    }
    if(n!=1) cout<<n<<" "<<1<<endl;
    return 0;
}

• Time Complexity: O(sqrt(n) * number of prime factors)
• Space Complexity: O(1)

Giải pháp này chỉ kiểm tra các số i từ 2 đến sqrt(n). Nếu i là ước của n, nó kiểm tra xem i có phải là số nguyên tố hay không bằng hàm check_nt(). Nếu đúng, nó đếm số mũ và in ra. Tuy nhiên, giải pháp này không hiệu quả vì:

1. Nó gọi check_nt() cho mỗi i, tốn thêm O(sqrt(i)) time.
2. Nó có hai vòng lặp lồng nhau không cần thiết.
3. Nó loại bỏ các số không nguyên tố trước, nhưng thực tế nếu i chia hết n thì i phải là tích của các số nguyên tố nhỏ hơn, đã được xử lý trước đó. Về cơ bản, đây là cách tiếp cận không tối ưu về thời gian执行.

Cách Optimized Trial Division

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    vector<pair<long long, int>> factors;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            factors.push_back({i, count});
        }
    }
    if (n > 1) {
        factors.push_back({n, 1});
    }
    std::cout << factors.size() << endl;
    for (const auto& factor : factors) {
        cout << factor.first << " " << factor.second << endl;
    }
    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Đây là cách tiếp cận chuẩn để phân tích số nguyên tố. Nó hoạt động như sau:

1. Duyệt i từ 2 đến sqrt(n).
2. Nếu n chia hết cho i, thì i là thừa số nguyên tố đầu tiên. Đếm số mũ bằng cách chia n cho i liên tục.
3. Sau vòng lặp, nếu n > 1 thì n còn lại chính là một số nguyên tố lớn hơn sqrt(n) ban đầu. Độ phức tạp là O(sqrt(n)) vì chúng ta chỉ duyệt đến căn bậc hai của n. Với n ≤ 10^12, sqrt(n) ≤ 10^6, hoàn toàn khả thi. Giải pháp này hiệu quả và phổ biến trong lập trình thi đấu.

Cách Hash Map / Dictionary Approach

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
map < ll , ll > mp;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    if ( n <= 1 ) {
        cout << 0 ;
        return 0 ;
    }
    ll i = 2;
    while ( i * i <= n ) {
        while ( n % i == 0 ) {
            mp [ i ]++ ;
            n /= i ;
        }
        i++ ;
    }
    if ( n > 1 ) mp [ n ]++ ;
    cout << mp.size() << endl ;
    for ( auto x : mp ) cout << x.first << " " << x.second << "\n" ;
    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(log n) (số lượng phần tử trong map)

Cách tiếp cận này tương tự như 'Optimized Trial Division' nhưng sử dụng std::map hoặc std::vector (giải pháp 2) để lưu trữ kết quả. Cấu trúc dữ liệu map cho phép tự động sắp xếp các thừa số nguyên tố theo thứ tự tăng dần và dễ dàng quản lý số mũ. Quy trình:

1. Duyệt i từ 2 đến sqrt(n).
2. Nếu n chia hết cho i, dùng map để đếm số mũ.
3. Nếu n > 1 sau vòng lặp, thêm n vào map với số mũ là 1. Độ phức tạp thời gian vẫn là O(sqrt(n)), nhưng truy cập map có chi phí O(log K) (K là số lượng phần tử), có thể bỏ qua. Giải pháp này linh hoạt nếu bạn muốn xử lý các thừa số ngẫu nhiên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Chỉ cần duyệt đến căn bậc hai của n (sqrt(n)) để tìm các thừa số nguyên tố. Nếu sau vòng lặp n vẫn còn > 1, thì n đó chính là một thừa số nguyên tố (vì nó không có ước nhỏ hơn hoặc bằng sqrt(n)).
• Phải chia n cho i liên tục trong khi n chia hết cho i để đếm đúng số mũ của thừa số đó trước khi chuyển sang số tiếp theo.
• Với n ≤ 10^12, độ phức tạp O(sqrt(n)) ≈ 10^6 thao tác là hoàn toàn chấp nhận được.

Lỗi thường gặp

• Sử dụng biến int cho n và các biến vòng lặp. Với n lên tới 10^12, cần dùng long long (hoặc int64_t) để tránh tràn số.
• Quên kiểm tra trường hợp n > 1 sau vòng lặp. Nếu bỏ qua, sẽ mất thừa số nguyên tố lớn nhất.
• Kiểm tra tính nguyên tố của i trước khi chia n (như Solution 1) là không cần thiết và gây chậm chương trình. Nếu i chia hết n, thì i phải là tích của các thừa số nguyên tố nhỏ hơn đã được xử lý trước đó, nên về bản chất i sẽ là số nguyên tố tại thời điểm đó.