概要
愚直な方法では正解できません．
求めるべきことを明らかにして考えてみましょう．
問題原案：kusirakusira
解説
操作後の の要素は非常に大きくなりうるため，実際に操作を再現して答えを求めることは難しいです．
別なアプローチを考えてみましょう．
を 番目に小さい素数とします．
整数 の約数の個数は と表されます．
のもつ 番目の素因数を 個以上 個以下選ぶ組み合わせの総数です．
の値を，ベクトル として持つことを考えます．
すると， 回の操作は各々次のように言い換えることができます：
- とする．
- を満たす任意の整数 について：
- を で置換する．
以上の操作はimos法を用いるなどして簡単に実装できます．
求めるべきは， として， です．
なお実際には より各ベクトルの要素数は高々 で十分と分かります．これは 以下の素数の個数です．
解説：uni_kakurenbo