はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるエラトステネスの篩・区間篩問題

uwiさんの最強まとめ

エラトステネスの篩

  • 本来は素数列挙のためのアルゴリズム 解説
  • rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く
  • 以下の問題はエラトステネスの篩以外にも上のループ構造のお陰で計算量がO(NlogN)に落ちる問題も入れてある

区間

問題


以下、解説やメモなど



















Codeforces 376 F. Video Cards

http://codeforces.com/contest/731/problem/F
この問題のEditorialで書いてある方程式は覚えておくと便利そう。
エラトステネスがO(n log n)である理由が書いてある。
倍数を全て全探索する場合はO(n log n)で収まることを覚えておこう。
解説
http://codeforces.com/blog/entry/47840
http://kmjp.hatenablog.jp/entry/2016/10/16/1030

SRM 703 Mid DAGConstruction

https://community.topcoder.com/stat?c=problem_statement&pm=14461
「倍数を全て全探索する場合はO(n log n)で収まること」が使えた回。
これだ!と思ったので、追記。
gcdを倍数に読み替えて辺を貼って、連結性を見る感じ。

Educational Codeforces Round 20 F. Coprime Subsequences

http://codeforces.com/contest/803/submission/26796820
包除原理も使う。
hamayanhamayan.hatenablog.jp