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

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

hamayanhamayan's blog

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

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

Educational Codeforces Round 20 F. Coprime Subsequences


以下、解説やメモなど



















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