Hiểu bài toán

Bài toán yêu cầu tính tổng số mũ của các thừa số nguyên tố trong phân tích thừa số nguyên tố của số n, được chia thành hai nhóm: tổng số mũ chẵn và tổng số mũ lẻ.

Cụ thể:

• Cho số nguyên dương n.
• Phân tích n thành tích các thừa số nguyên tố: n = p1^e1 * p2^e2 * ... * pk^ek.
• Gọi tổng số mũ chẵn là S = sum(ei) với ei chẵn.
• Gọi tổng số mũ lẻ là P = sum(ei) với ei lẻ.
• In ra S và P.

Ví dụ: n = 12 = 2^2 * 3^1

• Số mũ chẵn: 2 (từ 2^2) -> S = 2
• Số mũ lẻ: 1 (từ 3^1) -> P = 1

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

Cách Sàng Eratosthenes và Phân tích thừa số

#include <bits/stdc++.h>
using namespace std;
long long n, chan = 0, le = 0, dd[1000005];
bool nt[1000005];
void snt(){
    nt[0] = false;
    nt[1] = false;
    for(long long i = 2;i <= 1000000;i++){
        nt[i] = true;
        dd[i] = 0;
    }
    for(long long i = 2;i <= sqrt(1000000);i++){
        if(nt[i]){
            for(long long j = i * i;j <= 1000000;j += i){
                nt[j] = false;
            }
        }
    }
}
int main(){
    freopen("SumExpo.inp", "r", stdin);
    freopen("SumExpo.out", "w", stdout);
    snt();
    cin >> n;
        for(long long i = 2;i <= 1000000;i++){
            if(nt[i] && n % i == 0) {
              while(n % i == 0){
                dd[i]++;
                n /= i;
            }
        }
    }
  if(n > 1) le++;
    for(int i = 0;i <= 1000000;i++){
        if(dd[i] % 2 == 0) chan += dd[i];
        else le += dd[i];
    }
    cout << chan << "\n" << le;
    return 0;
}

• Time Complexity: O(N log log N + sqrt(N)) ~ O(10^6)
• Space Complexity: O(N) ~ O(10^6)

Phương pháp này sử dụng sàng Eratosthenes để tạo trước mảng các số nguyên tố jusquị 10^6. Sau đó, nó duyệt qua các số nguyên tố này để phân tích n:

1. Sàng tạo mảng nt[] đánh dấu số nguyên tố và mảng dd[] lưu số mũ.
2. Duyệt i từ 2 đến 10^6, nếu i là nguyên tố và chia hết cho n thì đếm số mũ.
3. Nếu sau vòng lặp n > 1 thì n là số nguyên tố lớn hơn 10^6, cộng 1 vào tổng số mũ lẻ.
4. Duyệt lại mảng dd để cộng dồn vào S (chẵn) hoặc P (lẻ).

Ưu điểm: Dễ hiểu, ổn định. Nhược điểm: Giới hạn bởi N = 10^6, tốn bộ nhớ.

Cách Phân tích thừa số nguyên tố tối ưu

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("SumExpo.inp", "r", stdin);
    freopen("SumExpo.out", "w", stdout);
    int n, S = 0, P = 0;
    cin >> n;
    map<int, int> mp;
    while (n % 2 == 0)
    {
        mp[2]++;
        n /= 2;
    }
    for (int i = 3; i * i <= n; i += 2)
    {
        while (n % i == 0)
        {
            mp[i]++;
            n /= i;
        }
    }
    if (n > 1) mp[n]++;
    for (auto it: mp)
    {
        if (it.second % 2 == 0) S += it.second;
        else P += it.second;
    }
    cout << S << "\n" << P;
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(log N)

Phương pháp này chia làm 2 giai đoạn:

1. Xử lý riêng thừa số 2: Lặp khi n chia hết cho 2, đếm số mũ.
2. Xử lý các số lẻ từ 3 đến sqrt(n): Duyệt i với bước nhảy 2 (chỉ kiểm tra số lẻ). Khi n chia hết cho i, đếm số mũ và chia n cho i.
3. Nếu sau vòng lặp n > 1 thì n là số nguyên tố, thêm vào map.
4. Duyệt map để tính tổng S và P.

Ưu điểm: Tối ưu, không cần bộ nhớ lớn, chạy nhanh cho n lớn (lên tới 10^12). Nhược điểm: Cần xử lý đúng bước nhảy 2 và kiểm tra biên.

Cách Phân tích thừa số với vector và hash map

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

const int N=1E6+7;
vector<int> a;
unordered_map<int,int> b;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("SUMEXPO.INP","r",stdin);
    freopen("SUMEXPO.OUT","w",stdout);
    long long n;
    cin>>n;
    int i=2;
    while (i*i<=n){
        if (n%i==0){
            a.push_back(i);
            while (n%i==0){
                n/=i;
                b[i]++;
            }
        }
        i++;
    }
    if (n>1){
        a.push_back(n);
        b[n]++;
    }
    long long tong_chan=0;
    long long tong_le=0;

    for (auto it: a){
        if (b[it]%2==0) tong_chan+= b[it];
        else tong_le+= b[it];
    }

    cout<<tong_chan<<' '<<tong_le;
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(log N)

Phương pháp tương tự Approach 2 nhưng sử dụng vector để lưu các thừa số và unordered_map để lưu số mũ:

1. Duyệt i từ 2 đến sqrt(n).
2. Nếu n chia hết cho i, thêm i vào vector và đếm số mũ trong unordered_map.
3. Nếu sau vòng lặp n > 1, thêm n vào vector và map.
4. Duyệt vector để tính tổng S và P.

Ưu điểm: Tương đối tối ưu, dễ dàng truy cập các thừa số. Nhược điểm: Tốn bộ nhớ hơn Approach 2 một chút do lưu vector.

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

Bài học kinh nghiệm

• Bài toán chỉ quan tâm đến tính chẵn/lẻ của số mũ, không cần giá trị chính xác của n sau phân tích.
• Sau khi tìm được số mũ ei của mỗi thừa số nguyên tố, ta chỉ cần kiểm tra ei % 2 == 0 để quyết định cộng vào S hay P.
• Có thể tối ưu bằng cách xử lý thừa số 2 riêng và chỉ duyệt các số lẻ từ 3 trở đi, giảm một nửa số lần lặp.
• Nếu n có giá trị lớn (ví dụ > 10^12), cần sử dụng thuật toán phân tích thừa số nguyên tố O(sqrt(n)) thay vì sàng mảng.

Lỗi thường gặp

• Quên kiểm tra trường hợp n > 1 sau vòng lặp phân tích thừa số (trường hợp n là số nguyên tố lớn hơn sqrt(n) ban đầu).
• Sử dụng biến số mũ sai kiểu (ví dụ dùng int cho long long), gây tràn số.
• Trong Approach 1, nếu n < 10^6 nhưng có thừa số nguyên tố > 10^6, cần xử lý riêng (code mẫu đã xử lý bằng cách kiểm tra n > 1).
• Lỗi vị trí fread/fwrite: Tên file phải khớp chính xác (có thể khác hoa/thường).
• Bỏ qua việc tối ưu duyệt số lẻ trong vòng lặp (nếu dùng i++ thay vì i+=2).