読者です 読者をやめる 読者になる 読者になる

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

hamayanhamayan's blog

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

思いついたので、まとめました
エラトステネスの篩はWikipediaが動画付きで分かりやすいです
https://ja.wikipedia.org/wiki/エラトステネスの篩
本来は素数判定のアルゴリズムですが、エラトステネスっぽい感じ(主観)な問題があったので、それのまとめです。

SRM 703 Mid DAGConstruction

https://community.topcoder.com/stat?c=problem_statement&pm=14461


以下、解説やメモなど

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を倍数に読み替えて辺を貼って、連結性を見る感じ。