823 : 素因数シャッフル

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

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

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

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

最終更新

役に立ちましたか?