水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Beginner Contest 110:D - Factorization

問題

D - Factorization

解法

M を素因数分解する.M の各素因数を N 個の箱に分けていくと考えればよい.このとき,単純に N ^ (各素因数の個数) を掛け合わせたものを答えにしてしまうと,重複が生まれてしまう.なので,重複組み合わせ H(n, r) = C(n+r-1, n) を使う.このとき,逆元などを用いた Combination を使う必要がある(制約が大きいので).

解答

M = 1 のコーナーケースで 1 WA をしてしまった.

Submission #3256550 - AtCoder Beginner Contest 110

f:id:babcs2035:20180924141314p:plain