Factorization [AtCoder Beginner Contest 110 D]

https://beta.atcoder.jp/contests/abc110/tasks/abc110_d

前提知識

• 素因数分解
• nHk mod 素数

解法

https://beta.atcoder.jp/contests/abc110/submissions/3260162

数列aにすべて1を入れておく。
すべてかけてMになるためには、Mを素因数分解して、できた素因数を分配していけばいい。
まずはMを素因数分解する。
ある素因数p^mについて、m個のpをn個に分配するが、これは重複組合せで実現できる。
具体的にはnHmである。
これをすべての素因数について求めて、総積を取ると答え。

int N, M;
Comb<mint, 201010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    auto ep = enumpr(M);
 
    mint ans = 1;
    fore(p, ep) ans *= com.nHk(N, p.second);
    cout << ans << endl;
}