Số Cách Phân Tích Thừa Số

Lời giải: Số Cách Phân Tích Thừa Số

Hướng tiếp cận

Dùng phân tích thừa số nguyên tố kết hợp công thức tổ hợp (stars and bars).

Nhận xét quan trọng

1. Phân tích $m=p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_k^{e_k}$.
2. Vì các thừa số nguyên tố độc lập nhau, số cách phân tích $m$ thành tích của $n$ số bằng tích của số cách phân phối từng lũy thừa.
3. Số cách phân phối $e_i$ đơn vị của $p_i$ vào $n$ vị trí (mỗi vị trí nhận $\ge 0$) = $\left(\genfrac{}{}{0ex}{}{e_i+n-1}{n-1}\right)$ (công thức stars and bars).

Thuật toán

1. Phân tích từng $a_j$ ra thừa số nguyên tố, cộng dồn số mũ vào cnt[p].
2. Với mỗi số nguyên tố $p$ có tổng số mũ $e$, nhân kết quả với $\left(\genfrac{}{}{0ex}{}{e+n-1}{n-1}\right)\left(\mathrm{mod}{10}^9+7\right)$.
3. Tính $\left(\genfrac{}{}{0ex}{}{e+n-1}{n-1}\right)$ qua giai thừa và nghịch đảo modulo.

Độ phức tạp

• Thời gian: $O(n\sqrt{maxa})$ để phân tích thừa số, $O(\text{MAXF})$ để tiền xử lý giai thừa
• Bộ nhớ: $O(\text{MAXF})$