[yukicoder] No. 847 Divisors of Power

問題

方針

素因数分解

\( N \) を素数 \( p_i \) と 正の整数 \( a_i \) を用いて、 \( N = p_1^{a_1}p_2^{a_2} \cdots p_n^{a_n} \) と表すと、

\[ N^K = p_1^{a_1K}p_2^{a_2K} \cdots p_n^{a_nK} \]

と表現できます。\( N^K \) の約数を、\( f(b_1, b_2, \cdots, b_n) \ (0 \leq b_i \leq a_iK)\) とすると、

\[ f(b_1, b_2, \cdots, b_n) = p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}\]

となります。

深さ優先探索

\( f(b_1, b_2, \cdots, b_n) \) の \( b_i \) 組み合わせを全探索します。どのように全探索をするかというと、深さ優先探索で、枝刈りをしながら行います。下の図がイメージになります。

 

探索のイメージ

掛け算を行いながら深さ優先探索を行うので、その値が \( M \) を超えたとき、その探索を止めます。

コード