Hiểu bài toán

Cho một số nguyên dương N. Yêu cầu phân tích N thành thừa số nguyên tố, sau đó tính và in ra:

• Dòng 1: Tổng độ mũ của các thừa số nguyên tố có độ mũ chẵn.
• Dòng 2: Tổng độ mũ của các thừa số nguyên tố có độ mũ lẻ. Ví dụ: N = 12 = 2^2 * 3^1. Thừa số 2 có độ mũ 2 (chẵn), thừa số 3 có độ mũ 1 (lẻ). Do đó tổng độ mũ chẵn là 2, tổng độ mũ lẻ là 1.

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

Cách Phân tích thừa số nguyên tố cơ bản

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

int main() {
    freopen("SumExpo.Inp", "r", stdin);
    freopen("SumExpo.Out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    int s = 0, q = 0;

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int d = 0;
            while (n % i == 0) {
                n /= i;
                d++;
            }
            if (d % 2 == 1) q += d;
            else s += d;
        }
    }

    if (n > 1) {
        q += 1;
    }

    cout << s << '\n' << q;
    return 0;
}

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

Đây là phương pháp phân tích thừa số nguyên tố trực tiếp. Ta duyệt các số i từ 2 đến căn bậc hai của N. Với mỗi i, nếu i là ước của N, ta đếm số lần N chia hết cho i (độ mũ d). Nếu d là số chẵn, cộng d vào biến s (tổng số mũ chẵn), nếu d là lẻ, cộng d vào biến q (tổng số mũ lẻ). Sau vòng lặp, nếu N còn lại lớn hơn 1, nghĩa là N hiện tại là một số nguyên tố có độ mũ là 1 (lẻ), nên ta cộng 1 vào q.

Cách Tối ưu hóa

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("SumExpo.Inp","r",stdin);
    freopen("SumExpo.Out","w",stdout);
    long long n;cin>>n;
    long long s=0,p=0;
    for(long long i=2;i*i<=n;i++){
        int c=0;
        while(n%i==0)n/=i,c++;
        if(c%2==0)s+=c;
        else p+=c;
    }
    if(n>1)p++;
    cout<<s<<endl<<p;
}

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

Đây là phiên bản ngắn gọn hơn của phương pháp 1, thường thấy trong các bài thi lập trình. Logic hoàn toàn giống nhau: phân tích N để tìm số mũ của mỗi thừa số nguyên tố. Tên biến được rút gọn (s cho even/sum, p cho odd) và cấu trúc code gọn hơn. Các bước thực hiện:

1. Duyệt i từ 2 đến sqrt(N).
2. Với mỗi i, đếm số lần N chia hết (c).
3. Nếu c chẵn, cộng vào s; nếu lẻ, cộng vào p.
4. Xử lý phần còn lại của N sau vòng lặp.

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

Bài học kinh nghiệm

• Bài toán yêu cầu chỉ phân tích thừa số nguyên tố, không cần tính giá trị thừa số, nên chỉ cần đếm số mũ (exponent) của mỗi thừa số.
• Chỉ cần duyệt đến căn bậc hai của N (i * i <= N) là đủ để tìm hết các thừa số nguyên tố.

Lỗi thường gặp

• Quên kiểm tra điều kiện n > 1 sau vòng lặp để xử lý trường hợp N là số nguyên tố hoặc chứa một thừa số nguyên tố lớn hơn căn bậc hai của N.
• Sử dụng biến lưu trữ số mũ có kiểu dữ liệu quá nhỏ (ví dụ: int hoặc short) cho N lớn, nhưng trong bài này số mũ thường nhỏ, dùng int là đủ. Tuy nhiên, biến N phải là long long để tránh tràn số khi nhập.
• Lỗi logic khi chia đôi số mũ: tổng số mũ chẵn và lẻ phải cộng dồn chính xác dựa trên giá trị d (số lần chia hết), không phải chỉ cộng 1.