n-knuu's logs

憧れ駆動。だいたい競プロ

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。ライブラリ整備しようと言ってかなり時間経っている気がする。

最後に

日刊とは何だったのか

*1:下のコードではmiller-rabinを使っているので、log^3(N)くらい

*2:miller-rabinを使ってないとTLEしそう