Phân tích thuật toán

Do ~ N ~ có thể lên tới ~ 10^{12} ~, duyệt toàn bộ từ ~ 1 ~ đến ~ N ~ để tìm ước số là quá chậm. Vì vậy, ta sử dụng phương pháp tối ưu dựa trên phân tích thừa số nguyên tố.

Phương pháp giải

1. Phân tích thừa số nguyên tố của ~ N ~

   • Ta tìm tất cả các thừa số nguyên tố ~ p ~ của ~ N ~ và số mũ ~ e ~ của chúng.
   • Nếu ~ N = 12 ~, ta có: ~ 12 = 2^2 \times 3^1 ~, tức là ~ \{2:2, 3:1\} ~.

2. Tính số lượng ước số

   • Công thức:
     ~ \text{countDiv} = (e_1 + 1) \times (e_2 + 1) \times ... \times (e_k + 1) ~
   • Ví dụ: ~ 12 = 2^2 \times 3^1 ~ → ~ (2+1) \times (1+1) = 6 ~.

3. Tính tổng ước số

   • Công thức:
     ~ \sum_{d \in divisors} d = \prod_{i=1}^{k} \frac{p_i^{e_i+1} - 1}{p_i - 1} ~
   • Ví dụ: ~ 12 ~ có tổng ước số:
     ~ \frac{2^3 - 1}{2-1} \times \frac{3^2 - 1}{3-1} = \frac{7}{1} \times \frac{8}{2} = 7 \times 4 = 28 ~

4. Tính tích ước số

   • Công thức:
     ~ P = N^{\frac{\text{countDiv}}{2}} \mod (10^9 + 7) ~
   • Ví dụ: ~ 12 ~ có tích ước số:
     ~ 12^{6/2} = 12^3 = 1728 ~

* Chương trình*

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

// Hàm tính (a^b) % MOD bằng phương pháp luỹ thừa nhị phân
ll powerMod(ll a, ll b, ll mod) {
    ll res = 1; a = a % mod;
    while (b) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// Phân tích thừa số nguyên tố của N, lưu vào vector<pair<ll, ll>>
vector<pair<ll, ll>> primeFactorize(ll N) {
    vector<pair<ll, ll>> factors;
    for (ll i = 2; i * i <= N; i++) {
        if (N % i == 0) {
            ll count = 0;
            while (N % i == 0) {
                count++;
                N /= i;
            }
            factors.push_back({i, count});
        }
    }
    if (N > 1) factors.push_back({N, 1}); // Nếu còn số nguyên tố lớn hơn sqrt(N)
    return factors;
}

// Hàm tính số lượng ước số
ll countDivisors(vector<pair<ll, ll>> &factors) {
    ll count = 1;
    for (auto &p : factors) {
        count *= (p.second + 1);
    }
    return count;
}

// Hàm tính tổng các ước số dựa vào công thức cấp số nhân
ll sumDivisors(vector<pair<ll, ll>> &factors) {
    ll sumDiv = 1;
    for (auto &p : factors) {
        ll prime = p.first;
        ll exp = p.second;
        ll term = (powerMod(prime, exp + 1, MOD) - 1 + MOD) % MOD;
        ll inv = powerMod(prime - 1, MOD - 2, MOD); // Tính (p-1)^(-1) mod MOD
        sumDiv = (sumDiv * term % MOD) * inv % MOD;
    }
    return sumDiv;
}

// Hàm tính tích ước số
ll productDivisors(ll N, ll countDiv) {
    ll exp = countDiv / 2; // Tích ước số = N^(số ước số / 2)
    return powerMod(N, exp, MOD);
}

int main() {
    ll N;
    cin >> N;

    // Phân tích thừa số nguyên tố
    vector<pair<ll, ll>> factors = primeFactorize(N);

    // Tính số lượng ước số
    ll countDiv = countDivisors(factors);

    // Tính tổng ước số
    ll sumDiv = sumDivisors(factors);

    // Tính tích ước số
    ll productDiv = productDivisors(N, countDiv);

    // In kết quả
    cout << countDiv << endl;
    cout << sumDiv << endl;
    cout << productDiv << endl;

    return 0;
}