Hiểu bài toán

Cho số nguyên dương N, xét T = N(N+1)(N+2). Yêu cầu đếm số lượng ước của T^2 mà nhỏ hơn T và không phải là ước của T.

Phân tích: Gọi d(x) là số lượng ước dương của số nguyên dương x. T là tích của 3 số nguyên dương liên tiếp nên T > 0. Ta cần đếm số lượng ước d của T^2 sao cho d < T và T không chia hết d.

Mối quan hệ giữa ước của T và ước của T^2: Nếu d là ước của T, thì d cũng là ước của T^2. Với mỗi ước d của T, ta có một ước tương ứng là T^2/d (cũng là ước của T^2). Trừ khi d = T (d * d = T^2), các ước của T tạo thành các cặp (d, T^2/d) mà tích của chúng là T^2. Trong một cặp (d, T^2/d), ước nào nhỏ hơn T?

• Nếu d < T, thì T^2/d > T.
• Nếu d > T, thì T^2/d < T.

Vậy, số lượng ước của T^2 nhỏ hơn T bằng:

1. Tüm các ước d của T sao cho d < T.
2. Các ước của T^2 không phải ước của T. Trong mỗi cặp (d, T^2/d) tạo thành từ các ước không phải của T, chính xác một ước nhỏ hơn T.

Tổng số ước của T^2 là d(T^2) = ∏ (2*ei + 1) với ei là số mũ của các thừa số nguyên tố trong T. Số ước của T là d(T) = ∏ (e_i + 1).

Ta có thể tính:

• Số lượng ước của T^2 nhỏ hơn T bằng một nửa của (Tổng số ước của T^2 - 1) cộng với số ước của T nhỏ hơn T. Công thức chính xác: Số lượng ước d của T^2 nhỏ hơn T = (d(T^2) - d(T)) / 2 + (d(T) - 1) = (d(T^2) - 1) / 2.

Giải thích:

• Các ước của T^2 được chia làm 3 loại:
  1. Các ước d của T (trừ T). Số lượng: d(T) - 1. Các ước này đều < T.
  2. Các ước d của T^2 mà không phải ước của T. Các ước này tạo thành cặp (d, T^2/d) với d * (T^2/d) = T^2. Nếu d không phải là ước của T, thì T^2/d cũng không phải là ước của T. Trong cặp này, một cái < T, một cái > T. Vậy có (d(T^2) - d(T))/2 ước loại này nhỏ hơn T.
  3. ước T (nếu xét). T = T.

Tổng số ước của T^2 nhỏ hơn T = (d(T) - 1) + (d(T^2) - d(T))/2 = (d(T^2) - 1)/2.

Bài toán yêu cầu đếm số ước của T^2 nhỏ hơn T và KHÔNG phải ước của T. Điều này tương đương với: (Số ước của T^2 nhỏ hơn T) - (Số ước của T nhỏ hơn T) = [(d(T^2) - 1)/2] - [(d(T) - 1)] = (d(T^2) - 1)/2 - d(T) + 1 = (d(T^2) - 2*d(T) + 1)/2

Kết quả là một số nguyên vì d(T^2) và d(T) có cùng tính chẵn/lẻ (d(T^2) là lẻ, d(T) có thể chẵn hoặc lẻ, nhưng (lẻ - 2*lẻ + 1) hoặc (lẻ - 2*lẻ + 1) đều chia hết cho 2).

Vấn đề cần giải quyết:

1. Phân tích N, N+1, N+2 thành các thừa số nguyên tố để tìm các thừa số nguyên tố của T và số mũ tương ứng.
2. Tính d(T) = ∏ (e_i + 1).
3. Tính d(T^2) = ∏ (2*e_i + 1).
4. Áp dụng công thức: (d(T^2) - 2*d(T) + 1) / 2.

Hạn chế:

• N <= 10^6.
• Q <= 10^5.
• Kết quả có thể rất lớn, cần sử dụng số lớn (trong C++ có thể dùng __int128 hoặc BigInt nhưng __int128 thường đủ nếu kết quả không vượt quá 2^128-1 ~ 3.4e38. Tuy nhiên, \d(T^2) có thể khá lớn. Ví dụ T có ~6-7 thừa số khác nhau, tổng số mũ ~10-15. \d(T^2) có thể lên tới ~3^15 ~ 1.4e7, vẫn vừa \long long. Nhưng nếu có nhiều thừa số và số mũ lớn hơn? N=10^6, T ~ 10^18. Số mũ primorial không lớn. __int128 an toàn).

Phân tích các solution:

• Solution 1 (nhuttruong2k9): Sử dụng sàng phân tích số nguyên tố (Sieve) để tìm số nguyên tố và phân tích N, N+1, N+2. Tính toán công thức.
• Solution 2 (oqtn75): Tương tự, dùng SPF (Smallest Prime Factor) để phân tích nhanh. Sử dụng __int128 để tránh tràn số. Logic tính toán (tauT2 + 1)/2 - tauT.
• Solution 3 (tranhungss1702): Phân tích số bằng cách lặp từ 2 đến sqrt(n). Sử dụng map để lưu trữ và gộp thừa số.

Các phương pháp này đều xoay quanh việc phân tích 3 số N, N+1, N+2.

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

Cách Phân tích số nguyên tố trực tiếp (Prime Factorization)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    vector<int> queries(Q);
    int max_n = 0;
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i];
        max_n = max(max_n, queries[i]);
    }

    // Sieve of Eratosthenes to find Smallest Prime Factor (SPF)
    // Limit needs to be max_n + 3 because we factor N, N+1, N+2
    int limit = max_n + 3;
    vector<int> spf(limit + 1);
    for (int i = 2; i <= limit; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            if ((int64)i * i <= limit) {
                for (int j = i * i; j <= limit; j += i) {
                    if (spf[j] == 0) spf[j] = i;
                }
            }
        }
    }

    for (int N : queries) {
        // Map to store exponents of prime factors of T = N*(N+1)*(N+2)
        // Key: prime, Value: exponent
        unordered_map<int, int> exponents;

        for (int v = N; v <= N + 2; ++v) {
            int x = v;
            // Factorize x using SPF
            while (x > 1) {
                int p = spf[x];
                int cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    cnt++;
                }
                exponents[p] += cnt;
            }
        }

        __int128 tau_T = 1;
        __int128 tau_T2 = 1;

        for (auto &kv : exponents) {
            int e = kv.second;
            tau_T *= (e + 1);
            tau_T2 *= (2 * e + 1);
        }

        // Formula: (tau(T^2) - 2*tau(T) + 1) / 2
        // Or: (tau(T^2) + 1)/2 - tau(T)
        __int128 ans = (tau_T2 + 1) / 2 - tau_T;

        // Output result
        // Since ans fits in long long for given constraints, we cast it
        cout << (long long)ans << "\n";
    }
    return 0;
}

• Time Complexity: O(Q * log(maxN)) cho việc factorization với SPF precomputed, hoặc O(Q * sqrt(maxN)) nếu không dùng SPF (Solution 3). Với SPF precompute là O(maxN log log maxN).
• Space Complexity: O(max_N)

Phương pháp này dựa vào việc tính toán số lượng ước của T và T^2 dựa trên phân tích thừa số nguyên tố.

1. Tiền xử lý: Xây dựng mảng spf (Smallest Prime Factor) để phân tích số nhanh chóng. Với N <= 10^6, ta cần sàng đến 10^6 + 3.
2. Xử lý từng test case:
   • Duyệt qua 3 số N, N+1, N+2.
   • Sử dụng mảng spf để phân tích từng số và cộng dồn số mũ vào map exponents.
   • Sau khi có đầy đủ số mũ e_i cho các thừa số của T, tính d(T) = ∏(e_i + 1) và d(T^2) = ∏(2*e_i + 1).
   • Áp dụng công thức ans = (d(T^2) - 1)/2 - (d(T) - 1) = (d(T^2) - 2*d(T) + 1)/2.
   • Do kết quả có thể lớn, sử dụng __int128 để lưu trữ d(T) và d(T^2).

Độ phức tạp:

• Preprocessing: O(M log log M) với M ~ 10^6.
• Query: O(log N) để factorization (vì số lượng thừa số nguyên tố của N ~ log N). Với Q=10^5, tổng thời gian xử lý query rất nhanh (< 1s).
• Không gian: O(M) lưu mảng SPF.

Cách Hash Map phân tích từ sqrt (Solution 3 variant)

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

void factorize(int n, map<int, int>& mp) {
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }
    if (n > 1) mp[n]++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    while (Q--) {
        int N;
        cin >> N;
        map<int, int> exponents;
        // Phân tích 3 số N, N+1, N+2
        for (int v = N; v <= N + 2; ++v) {
            factorize(v, exponents);
        }

        __int128 tau_T = 1;
        __int128 tau_T2 = 1;

        for (auto& kv : exponents) {
            int e = kv.second;
            tau_T *= (e + 1);
            tau_T2 *= (2 * e + 1);
        }

        // Công thức: (d(T^2) - 2*d(T) + 1) / 2
        __int128 ans = (tau_T2 - 2 * tau_T + 1) / 2;

        cout << (long long)ans << "\n";
    }
    return 0;
}

• Time Complexity: O(Q * sqrt(max_N))
• Space Complexity: O(log N) cho map

Đây là cách tiếp cận đơn giản hơn, không cần tiền xử lý sàng.

1. Với mỗi test case, ta tạo một map (hoặc hash map) để lưu trữ các thừa số nguyên tố và số mũ của T.
2. Duyệt qua N, N+1, N+2. Với mỗi số, thực hiện phân tích thừa số bằng cách lặp từ 2 đến sqrt(số đó). Nếu i chia hết, ta chia cho i repeatedly và cập nhật map.
3. Sau khi map chứa đầy đủ thông tin về T, ta tính d(T) và d(T^2) và áp dụng công thức.

Phương pháp này chậm hơn phương pháp SPF khi Q lớn vì mỗi query tốn thời gian lặp lại các thao tác phân tích số. Tuy nhiên, với Q nhỏ (Q <= 10), nó hoàn toàn khả thi.

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

Bài học kinh nghiệm

• Công thức quan trọng: Số lượng ước của T^2 nhỏ hơn T và không phải ước của T là (d(T^2) - 2*d(T) + 1) / 2.
• Việc phân tích T = N(N+1)(N+2) có thể thực hiện bằng cách phân tích riêng N, N+1, N+2 và gộp kết quả, vì chúng là các số nguyên tố cùng nhau.
• Sử dụng __int128 là bắt buộc để tránh tràn số khi tính số lượng ước, ngay cả khi kết quả cuối cùng fits trong long long.

Lỗi thường gặp

• Tràn số khi tính tau(T^2): Cần kiểm tra giới hạn của long long. Với N=10^6, T có tối đa khoảng 10-12 thừa số nguyên tố khác nhau. d(T^2) có thể lớn.
• Hiểu sai yêu cầu bài toán: Yêu cầu là đếm ước của T^2 nhỏ hơn T KHÔNG phải ước của T. Nếu chỉ đếm ước của T^2 nhỏ hơn T, kết quả sẽ là (d(T^2)-1)/2.