E - 多段構成のコスト最小化

この問題は再帰関数と約数列挙を問います。

このような「条件を満たす組み合わせ」を求めるとき、かつ制約が小さい場合は再帰関数による列挙を行うことで解決できます。
今回の問題もそのような構造になっています。

問題文中にある $N=a_1\times a_2\times \dots\times a_M$ という条件から、これはすべての $i\ (1\le i\le M)$ に対して $N$ が $a_i$ で割り切れることと同値です。
逆にそうでなければ $N$ は $a_i$ の総積として表すことはできません。

これより $a_i$ の探索候補は $N$ の約数であることがわかります。
したがって約数列挙を用い、その候補の中から総積が $N$ となるような組み合わせを再帰関数によって求めればよいです。

しかし単純に「 $1$ から $N$ にするまで約数を乗じていく」という手法を取ると、あるケースによっては総積が $N$ を超えてしまうことがあります。
さらにそれは $64$ bit整数型に収まらない可能性もあります。

そのため、単純に乗じていくのではなく、「 $N$ から $1$ にするまで約数で割っていく」操作をすることが適切です。

この問題の最悪計算回数ですが、今回の制約から $N=720720,M=30$ のケースが最大となります※。
このケースでの計算回数は約 $1.3\times 10^6$ 回となりますが、十分高速です。よってこの問題を解くことができます。

解答例(C++):

※
この数字は高度合成数と呼ばれ、$10^6$ 以下の整数において約数の個数が最大となる数字です。厳密には $720720$ に対しては $240$ 個の約数が存在します。