ABC110 D - Factorization - ツバサの備忘録

解法

まずは素因数分解をし、それぞれの素因数についていくつ使われているかをカウントします。
こちらの記事と似たようなことをします。
$2$ ~ $\sqrt{m}$ までを全探索し、 $i$ が $m$ の約数である限り $m$ を $i$ で割り続け、その数をカウントしていきます。
探索後に、 $m$ がまだ $1$ でなければ、それは一番大きな素因数なので、それも個数1として別にカウントします。
そうしたら、その素因数を数列に配っていけばいいので、それぞれの素因数について配り方を考え、最後に積をとれば答えになります。
今回は数列の要素として1が許されているので、それぞれの素因数について、重複可能な組み合わせを考えていきます。
素因数を並べたあとに、 $n-1$ 個の仕切りをどう置くか、について考えるイメージです。これは、素因数の数をxとしたときに、 $x+n-1$ 個の中から仕切りの $n-1$ 個の選び方を数える問題に帰着できるので、
$_{n}H_x = _{x+n-1}C_{n-1} = _{x+n-1}C_{x}$
をそれぞれの素因数について計算すれば答えが求まります。