Hướng dẫn giải của Bài toán thừa số nguyên tố
Phân tích bài toán
Công thức tổng quát
Số lượng ước:
- Số lượng ước của ~ n = p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_n^{k_n} ~ là: ~ \text{num_divisors} = (k_1 + 1) \cdot (k_2 + 1) \cdot \ldots \cdot (k_n + 1) ~
Tổng các ước:
- Tổng các ước của ~ n ~ được tính bằng: ~ \text{sum_divisors} = \prod_{i=1}^{n} \frac{p_i^{k_i+1} - 1}{p_i - 1} ~ (dựa vào công thức của tổng cấp số nhân).
Tích các ước:
- Nếu số lượng ước là ~ d ~, tích các ước của ~ n ~ là: ~ \text{prod_divisors} = n^{d/2} ~
Tối ưu hóa
Modulo ~ 10^9 + 7 ~:
- Phép chia trong tổng ước sử dụng công thức nghịch đảo modular: ~ \frac{a}{b} \mod p = a \cdot b^{p-2} \mod p ~ với ~ p = 10^9 + 7 ~.
Lũy thừa nhanh:
- Tính ~ x^y \mod p ~ hiệu quả bằng thuật toán lũy thừa nhanh.
*Chương trình *
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7; // Số nguyên tố lớn để thực hiện modulo
const int maxN = 1e5; // Giới hạn số thừa số nguyên tố
int N;
ll x[maxN], k[maxN]; // Mảng lưu thừa số nguyên tố x[i] và số mũ k[i]
ll tau, sigma, mu, pi; // Lưu kết quả của τ(N), σ(N), P(N)
// Hàm lũy thừa nhanh a^b % MOD
ll fastpow(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1) res = (res * a) % MOD; // Nếu b lẻ, nhân thêm a vào kết quả
a = (a * a) % MOD; // Bình phương cơ số
b >>= 1; // Chia b cho 2
}
return res;
}
int main() {
// Nhập số thừa số nguyên tố
cin >> N;
for (int i = 0; i < N; i++)
cin >> x[i] >> k[i]; // Nhập thừa số nguyên tố và số mũ của nó
// **Tính số lượng ước số τ(N)**
tau = 1;
for (int i = 0; i < N; i++)
tau = (tau * (k[i] + 1)) % MOD; // Tính τ(N) = (k1+1) * (k2+1) * ...
// **Tính tổng các ước số σ(N)**
sigma = 1;
for (int i = 0; i < N; i++) {
ll numerator = (fastpow(x[i], k[i] + 1) - 1 + MOD) % MOD; // Tính x[i]^(k[i]+1) - 1
ll denominator = fastpow(x[i] - 1, MOD - 2); // Tính nghịch đảo modular của (x[i] - 1)
ll geoSum = (numerator * denominator) % MOD; // Tính tổng cấp số nhân
sigma = (sigma * geoSum) % MOD; // Nhân tổng vào kết quả chung
}
// **Tính tích các ước số P(N)**
pi = 1;
mu = 1;
for (int i = 0; i < N; i++) {
ll p = fastpow(x[i], k[i] * (k[i] + 1) / 2); // Tính x[i]^(k[i]*(k[i]+1)/2)
mu = fastpow(mu, k[i] + 1) * fastpow(p, pi) % MOD; // Cập nhật mu
pi = (pi * (k[i] + 1)) % (MOD - 1); // Cập nhật pi để tránh tràn số
}
// In kết quả
cout << tau << " " << sigma << " " << mu << endl;
return 0;
}