1 / 1

823 : 素因数シャッフル

リストは最初に数 $2, 3, \dots, n$ からなる。ラウンドごとに、リスト中の全ての数をその最小の素因数で割る。次に、それら最小の素因数の積を新たな数としてリストに追加する。最後に、1になった数を全てリストから除く。

例として、 $n=5$ の最初の3ラウンドを示す： $[2,3,4,5] \xrightarrow{(1)} [2,60] \xrightarrow{(2)} [30,4] \xrightarrow{(3)} [15,2,4]$

$m$ ラウンド後のリストの全ての数の和を $S(n,m)$ としよう。例えば、 $S(5,3) = 15 + 2 + 4 = 21$ である。また $S(10,100) = 257$ である。

$S(10^4, 10^{16}) \bmod 1234567891$ を求めよ。

例として、 $n=5$ の最初の3ラウンドを示す： $[2,3,4,5] \xrightarrow{(1)} [2,60] \xrightarrow{(2)} [30,4] \xrightarrow{(3)} [15,2,4]$

$m$ ラウンド後のリストの全ての数の和を $S(n,m)$ としよう。例えば、 $S(5,3) = 15 + 2 + 4 = 21$ である。また $S(10,100) = 257$ である。

$S(10^4, 10^{16}) \bmod 1234567891$ を求めよ。