Hiểu bài toán

Bài toán yêu cầu giải quyết các truy vấn về số nguyên. Với mỗi số nguyên dương N (trong phạm vi lên tới 10^6), bạn cần:

1. Tìm số lượng ước của N.
2. Liệt kê tất cả các thừa số nguyên tố của N theo số mũ tương ứng (ví dụ: 12 = 2^2 * 3^1 sẽ in ra "223").

Có nhiều truy vấn (t) cần xử lý. Input/Output được thực hiện qua file 'nto.inp' và 'nto.out'.

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

Cách Brute Force Phân tích thừa số nguyên tố (Tử số)

#include <bits/stdc++.h>
#define ll long long
using namespace std;

bool cx[1000011];
void sang(){
    for(ll i=1;i<=1000010;i++) cx[i]=true;
    cx[1]=false;
    for(ll i=2;i<=1000010;i++){
        if(cx[i]==true){
            ll j=i*i;
            while(j<=1000010){
                cx[j]=false;
                j+=i;
            }
        }
    }
}

ll demuoc(ll n){
    ll dem=0;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i==0){
            ll j=n/i;
            if(j!=i) dem+=2;
            else dem++;
        }
    }
    return dem;
}

int main() {
    freopen("nto.inp","r",stdin);
    freopen("nto.out","w",stdout);
    sang();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<demuoc(n)<<" ";
        for(ll i=2;i<=sqrt(n);i++){
            if(n%i==0 && cx[i]==true){
                cout<<i<<"*";
                n=n/i;
                while(n%i==0){
                    cout<<i<<"*";
                    n=n/i;
                }
            }
        }
        if(n>1) cout<<n;
        cout<<"\n";
    }
}

• Time Complexity: O(T * sqrt(N))
• Space Complexity: O(10^6)

Approach này tách biệt việc đếm ước và phân tích thừa số nguyên tố.

1. Sàng Eratosthenes: Tạo mảng cx đánh dấu số nguyên tố lên tới 10^6.
2. Đếm ước (demuoc): Duyệt từ 1 đến sqrt(N), nếu i chia hết N thì có cặp ước (i, N/i). Nếu hai số này bằng nhau thì cộng 1, ngược lại cộng 2.
3. Phân tích thừa số: Duyệt từ 2 đến sqrt(N). Nếu i là thừa số nguyên tố (kiểm tra bằng mảng cx) và chia hết N, ta in ra i và chia N cho i liên tục cho đến khi không còn chia hết. Cuối cùng nếu N còn lại > 1, in ra N.

Cách này có thể gây lỗi Logic Output nếu in thừa số theo thứ tự tăng dần nhưng chèn số mũ vào giữa (ví dụ: 12 in ra 223, nhưng cách này duyệt 2 trước rồi 3 sau là đúng). Tuy nhiên, cách đếm ước và cách in thừa số bị tách rời, dẫn đến việc duyệt lại các thừa số một cách không hiệu quả.

Cách Sàng phân tích thừa số (Prime Factorization Sieve)

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool notPrime[1000005];
vector<int> prime;

void Sieve() {
    for(int i = 2; i*i <= 1000000; i++)
        if(!notPrime[i])
            for(int j = i*i; j <= 1000000; j += i) notPrime[j] = true;
    for(int i = 2; i <= 1000000; i++)
        if(!notPrime[i]) prime.push_back(i);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    freopen("nto.inp", "r", stdin);
    freopen("nto.out", "w", stdout);

    Sieve();
    int t;
    cin >> t;

    while(t--) {
        int m;
        cin >> m;
        int res = 1, old = m;
        vector<int> ans;

        for(int p : prime) {
            if(p*p > old) break;

            int cnt = 0;
            while(old % p == 0) {
                ans.push_back(p);
                cnt++;
                old /= p;
            }
            if(cnt > 0) res *= (cnt + 1);
        }

        if(old > 1) {
            ans.push_back(old);
            res *= 2;
        }

        cout << res << " ";
        for(int i = 0; i < ans.size(); i++) {
            cout << ans[i];
            if(i != ans.size() - 1) cout << "*";
        }
        cout << "\n";
    }
}

• Time Complexity: O(T * (sqrt(N) / log(N)))
• Space Complexity: O(10^6)

Approach này sử dụng danh sách các số nguyên tố đã sàng để phân tích N.

1. Sàng Eratosthenes: Tạo vector prime chứa các số nguyên tố.
2. Xử lý từng số N:
   • Duyệt qua các số nguyên tố p trong vector prime. Chỉ cần duyệt tới p*p > N.
   • Với mỗi p, đếm số mũ cnt mà p chia hết N. Nếu cnt > 0, ta nhân res (số ước) với cnt + 1 và lưu p vào danh sách ans cnt lần.
   • Nếu sau vòng lặp N còn lại > 1, thì N lúc này là số nguyên tố còn lại, nhân res thêm 2 và thêm N vào ans.
3. In kết quả: In res và nối chuỗi ans bằng dấu *.

Cách này hiệu quả hơn cách 1 vì chỉ duyệt qua các số nguyên tố thực sự, giảm độ phức tạp từ O(sqrt(N)) xuống đáng kể (cỡ O(sqrt(N)/ln(N))).

Cách Sàng tối ưu (Optimized Sieve)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 1000000 + 5;

int tic[MAXN];
vector<int> fac[MAXN];
bool isPrime[MAXN];

void sieve() {
    fill(isPrime, isPrime + MAXN, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i < MAXN; ++i) {
        if (!isPrime[i]) continue;

        for (int j = i; j < MAXN; j += i) {
            isPrime[j] = false;
            int x = j;
            int cnt = 0;
            while (x % i == 0) {
                x /= i;
                ++cnt;
            }

            if (tic[j] == 0) tic[j] = 1;
            tic[j] *= (cnt + 1);

            // lưu i theo multiplicity
            for (int k = 0; k < cnt; ++k) {
                fac[j].push_back(i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("nto.inp", "r", stdin);
    freopen("nto.out", "w", stdout);

    sieve();

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        cout << tic[n] << " ";
        for (size_t i = 0; i < fac[n].size(); ++i) {
            cout << fac[n][i];
            if (i < fac[n].size() - 1) cout << "*";
        }
        cout << "\n";
    }
}

• Time Complexity: O(MAXN * log MAXN)
• Space Complexity: O(MAXN * A(N))

Đây là thuật toán tối ưu nhất, tiền xử lý toàn bộ dữ liệu trước khi nhận truy vấn.

1. Tiền xử lý (Sàng):
   • Duyệt qua từng số i từ 2 đến MAXN.
   • Nếu i là số nguyên tố, duyệt qua tất cả các bội số j của i (j = i, 2i, 3i...).
   • Với mỗi j, tính số mũ cnt của i trong j.
   • Cập nhật tic[j] (số ước) bằng cách nhân với (cnt + 1).
   • Thêm i vào fac[j] cnt lần để lưu thừa số.
2. Xử lý truy vấn:
   • Chỉ cần truy cập mảng tic[n] và vector fac[n] để in kết quả ngay lập tức.

Độ phức tạp tiền xử lý cao (khoảng 10^7 thao tác), nhưng xử lý truy vấn O(1). Rất nhanh cho T lớn.

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

Bài học kinh nghiệm

• Phép chia hết liên tục (while n % i == 0) là chìa khóa để tìm số mũ của thừa số nguyên tố.
• Công thức tính số ước từ phân tích thừa số: Nếu N = p1^a1 * p2^a2 * ... * pk^ak thì số ước của N là (a1+1)(a2+1)...*(ak+1).
• Sàng Eratosthenes có thể biến đổi để tìm thừa số nguyên tố cho tất cả các số trong một khoảng (Intelligent Sieve / Sieve of Eratosthenes for factorization), giúp xử lý nhiều truy vấn nhanh hơn.

Lỗi thường gặp

• Quên xử lý số còn lại cuối cùng (old > 1) sau vòng lặp phân tích thừa số, dẫn đến sai kết quả với số nguyên tố hoặc có thừa số nguyên tố lớn hơn sqrt(N).
• Lỗi in ra thứ tự sai (ví dụ in 232 thay vì 223) khi sử dụng các cấu trúc dữ liệu không sắp xếp hoặc duyệt sai.
• Sử dụng biến int 32-bit cho các phép nhân lớn khi tính số ước, dẫn đến tràn số (overflow). Nên dùng long long.
• Trong Approach 1 (Brute Force), việc đếm ước và in thừa số bị tách rời, dẫn đến việc duyệt thừa số 2 lần (một lần để đếm, một lần để in) hoặc logic in thừa số bị sai nếu chỉ in các thừa số chia hết ở bước đếm.