ABC110 D Factorization
数え上げ問題. ここで$ Mを素因数分解した後の数を$ N = p_1^{q_1}p_2^{q_2}..p_k^{q_k}とおき, $ p_iごとに考えて後から積の法則を用いることを考える. ここで$ p_iについて, $ a_1, a_2, ..., a_Nを$ p_iで割ったときの合計回数が$ q_iであればよいということがわかる. よって$ b_1 + b_2 + ... + b_N = q_iとすると, このような数列$ bは何通り存在するか調べればよいことになった. これは重複組合せなので, $ _{N + q_i - 1} C _{q_i}を計算することで求められる. 計算量は$ O(N)となる.