SRM672 div.1 250 Procrastination
解法
素数pに対して、pとp+1で仕事の交換が起こらないということを考えると、nより小さい最大の素数p1とn以上の最小の素数p2を見つけて、その間でシミュレーションすればよいことがわかる。
どうやってシミュレーションするかというと、p1からp2の各数について約数を全て求めて、辞書に各約数ごとに各数を記録(つまり、辞書型の変数dについて、d[i]=(p1以上p2以下の数のうち、iより大きいかつiで割り切れる数のリスト)となるようにする)しておき、小さい約数から順にswapしていけばよい。
計算量
- 素数の間隔: N以下の数に対して平均log(N)
- 数Nについて、素数判定にO(√N)*1、約数の列挙にO(√N)
- シミュレーションは、約数の個数回だけswapが行われる
- 数Nに対して、約数の個数は高々2√Nなので、平均2√N * log(N)
よって、平均√N * log(N)くらいと考えられる
コード
感想
素数のgapが600以下みたいな話題を最近見ていたのでそれが役に立った
C++の素数/約数ライブラリを持っていなくてpythonで書いたけど、初期コードでpythonだと最大1.911sec(TimeLimit 2sec)→1.7secになった*2。ライブラリ整備しようと言ってかなり時間経っている気がする。
最後に
日刊とは何だったのか