問題

正整数 $N, M$ が与えられる。 $a_1 * a_2 * ... * a_N = M$ となる a の数列が何通りあるか求めよ。

考え方

例として $2^3 * 3^2 * 5^2 = 1800, N = 4$ とする。

まずは $M$ を素因数分解をする。それぞれの因数ごとに独立して考えることができる。因数ごとのべき乗の数がポイントである。

$2^3$ を x x x x のような $4$ つのマスに配る配り方の場合の数を考える。左から $a, b, c, d$ ( $a, b, c, d$ は非負数)個あるような配り方を考えると、 $a + b + c + d = 4$ となるような $3$ つの $2$ を配る場合の数と同じである。

これは重複組合せで求めることができる。上の例であれば ${}_{4 + 3 - 1} \mathrm{C}_4$ で求めることができる。 $3$ の配り方、 $5$ の配り方も同様に ${}_{4 + 2 - 1} \mathrm{C}_4$ と ${}_{4 + 2 - 1} \mathrm{C}_4$ と求めることができ、解はそれぞれをかけ合わせればいい。