Hướng dẫn giải của [2526 VTT THPT KS2] Bài 4: Số cách nhân [MULARR1]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm các dãy ~n~ số nguyên dương có tích bằng ~m~. Mỗi thừa số nguyên tố ~p^e~ của ~m~ được chia độc lập cho ~n~ vị trí.
Sub 1: Quy hoạch động theo tích — dùng khi ~n \le 20,\ m \le 1000~
Gọi ~f[k][v]~ là số dãy độ dài ~k~ có tích ~v~; ~f[k][v] = \sum f[k-1][v/d]~ theo các ước ~d~ của ~v~. Nếu chỉ nộp sub này: đúng 12/43 test.
Sub 2: Phân tích thừa số nguyên tố và tổ hợp — ~O(\sqrt{m} + \text{số mũ} \cdot e)~
Phân tích ~m = p_1^{e_1} \cdots p_t^{e_t}~ bằng chia thử đến ~\sqrt{m} \le 10^6~. Chia số mũ ~e_i~ vào ~n~ vị trí (mỗi vị trí nhận một số mũ không âm) có ~\binom{e_i + n - 1}{e_i}~ cách, tính bằng ~(n)(n+1)\cdots(n+e_i-1) / e_i!~ theo modulo ~10^9+7~ (dùng nghịch đảo modular; ~e_i \le 40~). Đáp án là tích các giá trị này. Nếu chỉ nộp sub này: đúng 43/43 test.
Chương trình hoàn chỉnh
Hàm main đọc file MULARR1.INP, ghi MULARR1.OUT; ~n \le 20~ và ~m \le 1000~ gọi sub1 (12 test), còn lại gọi sub2 (31 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long n, m;
// Sub 1: quy hoạch động theo tích — dùng khi n <= 20, m <= 1000
// f[k][v] = số dãy độ dài k có tích bằng v; f[k][v] = tổng f[k-1][v/d] theo các ước d của v
void sub1() {
int M = m;
vector<vector<long long>> f(n + 1, vector<long long>(M + 1, 0));
f[0][1] = 1;
for (int k = 1; k <= n; k++)
for (int v = 1; v <= M; v++)
for (int d = 1; d <= v; d++)
if (v % d == 0) f[k][v] = (f[k][v] + f[k - 1][v / d]) % MOD;
cout << f[n][M] << "\n";
}
// Sub 2: phân tích ra thừa số nguyên tố m = p1^e1 * ... * pt^et.
// Mỗi số mũ ei được chia vào n vị trí độc lập: C(ei + n - 1, ei) cách. Đáp án là tích các tổ hợp đó.
long long power(long long b, long long e) {
long long r = 1; b %= MOD;
for (; e; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
void sub2() {
vector<int> exps;
long long x = m;
for (long long p = 2; p * p <= x; p++) {
if (x % p) continue;
int e = 0;
while (x % p == 0) x /= p, e++;
exps.push_back(e);
}
if (x > 1) exps.push_back(1);
long long ans = 1;
for (int e : exps) {
// C(e + n - 1, e) = (n)(n+1)...(n+e-1) / e!
long long num = 1, den = 1;
for (int i = 0; i < e; i++) {
num = num * ((n + i) % MOD) % MOD;
den = den * (i + 1) % MOD;
}
ans = ans * num % MOD * power(den, MOD - 2) % MOD;
}
cout << ans << "\n";
}
int main() {
freopen("MULARR1.INP", "r", stdin);
freopen("MULARR1.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
if (n <= 20 && m <= 1000) sub1();
else sub2();
return 0;
}
Bình luận