Codeforces ラウンド #226 (ディビジョン 2) C 数値理論_html/css_WEB-ITnose

タイトル:

CF マシンは非常に強力です。実行時間はわずか 600 ミリ秒で、n 個の数値を与えてから m 回質問するたびに、そのシーケンス内の各数値が範囲内にあるかどうかを調べます。間隔 [a, b] いくつかの素数の倍数を数え、その数を合計します。質問の下のヒントを読むと、a と b の範囲が少し広いことがわかります。大きい、2*10^9 の対処法がわかりませんが、後でシーケンス内の最大数は 10^7 であることがわかり、a と b がいくら大きくても問題ありません。数列の最大数より大きい素数の部分については、数列中にその倍数となる数が存在しないので、10^7 以内の素数を前処理して数を数えます。数列内で素数を前処理する際に、素数の倍数をふるい落とす処理が行われます。ここで、 の数を加算すると、数列内に素数の倍数が含まれているかどうかを判断できます。数値を調べ、最後に接頭辞の合計を見つけます。答えは sum[b] - sum[a - 1],

素数をスクリーニングする場合、2 番目の for ループは通常 2*i から始まりますが、保証はありませんたとえば、最初のケースでは、シーケンスに 5 があり、5 は 5 の倍数です。2 番目のレベルのループが 2*i から始まる場合、I'm はミスされます。ここでの通常の書き方では、デバッグが簡単ではないため、しばらく行き詰まってしまいました。