Hiểu bài toán

Bài toán yêu cầu với mỗi testcase gồm hai số nguyên dương N và p, tính tổng số lần p chia hết cho các số từ 1 đến N. Nói cách khác, ta cần tìm tổng số lượng thừa số p trong phân tích thừa số nguyên tố của tất cả các số từ 1 đến N. Công thức này thường được gọi là Legendre's Formula: $Ep(N!) = \sum{k=1}^{\infty} \lfloor \frac{N}{p^k} \rfloor$.

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

Cách Brute Force (Duyệt)

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

int countPowerOfPrime(int n, int k) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        int num = i;
        while (num % k == 0) {
            count++;
            num /= k;
        }
    }
    return count;
}

int main() {
    freopen("powerofprime.inp", "r", stdin);
    freopen("powerofprime.out", "w", stdout);

    int t;
    cin >> t;

    vector<pair<int, int>> queries(t);
    for (int i = 0; i < t; ++i) {
        cin >> queries[i].first >> queries[i].second;
    }

    for (int i = 0; i < t; ++i) {
        int n = queries[i].first;
        int k = queries[i].second;
        cout << countPowerOfPrime(n, k) << endl;
    }

    return 0;
}

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

Phương pháp này duyệt qua từng số từ 1 đến N. Với mỗi số i, nó kiểm tra xem p chia hết i bao nhiêu lần bằng cách lặp while. Ví dụ, nếu N = 10^6, vòng lặp này sẽ chạy khoảng 10^6 lần, và trong trường hợp xấu nhất (p=2, i rất lớn), số bước lặp có thể nhiều. Tuy nhiên, do bài này chạy trên máy cũ hoặc input nhỏ, phương pháp này có thể qua được. Tốc độ chậm, không khả thi với N lớn (ví dụ 10^9).

Cách Legendre Formula (Quy hoạch)

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

ll legendre(ll n, ll x) {
    ll cnt = 0;
    for (ll i = x; i <= n; i *= x) {
        cnt += (n / i);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("powerofprime.inp", "r", stdin);
    freopen("powerofprime.out", "w", stdout);
    int t = 1;
    cin >> t;
    while(t--) {
        ll n, x;
        cin >> n >> x;
        cout << legendre(n, x) << '\n';
    }
    return 0;
}

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

Đây là phương pháp chuẩn dùng công thức Legendre. Thay vì duyệt từng số, ta tính trực tiếp số lượng thừa số p trong N!. Số lượng thừa số p bằng tổng số bội của p, cộng số bội của p^2, v.v. (vì mỗi bội của p^2 được tính 2 lần). Vòng lặp i *= x dừng khi i > n, độ phức tạp logarit.

Cách Optimized Legendre (Xử lý tràn số)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("powerofprime.inp", "r", stdin);
    freopen("powerofprime.out", "w", stdout);

    int T;
    cin >> T;

    while (T--) {
        long long N, p;
        cin >> N >> p;

        long long k = 0;
        long long pw = p;

        while (pw <= N) {
            k += N / pw;
            if (pw > (long long)1e18 / p) break;
            pw *= p;
        }

        cout << k << "\n";
    }

    return 0;
}

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

Đây là phiên bản tối ưu và an toàn của Legendre Formula. Vấn đề của các giải pháp khác là khi p nhỏ và N lớn, biến pw (p^k) có thể tràn số (overflow) trước khi pw vượt quá N. Ví dụ pw * p có thể vượt quá giới hạn của long long. Dòng code if (pw > (long long)1e18 / p) break; kiểm tra xem phép nhân tiếp theo có gây tràn số không, nếu có thì dừng vòng lặp sớm để tránh lỗi.

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

Bài học kinh nghiệm

• Bài toán này yêu cầu tính tổng số lượng thừa số p trong phân tích các số từ 1 đến N.
• Công thức Legendre là cách tiếp cận hiệu quả nhất: $\sum \lfloor N/p^k \rfloor$.
• Nếu làm thủ công, có thể dùng while(N > 0) { N /= p; ans += N; } (vì $\lfloor N/p \rfloor + \lfloor N/p^2 \rfloor + ...$ chính là tổng số bội).

Lỗi thường gặp

• Tràn số (Integer Overflow): Khi tính lũy thừa p (pw = pw * p), nếu p lớn hoặc số lần lặp nhiều, biến pw có thể vượt quá giới hạn của kiểu dữ liệu long long. Cần kiểm tra tràn số trước khi nhân.
• Kiểu dữ liệu: N có thể lên tới 10^12 hoặc hơn, bắt buộc phải dùng long long (hoặc unsigned long long).