エラトステネスの篩
調和級数的計算量
- エラトステネスの篩がO(NlogN)で計算できるというような計算量の考え方を調和級数的計算量みたいに表現したりもする
- つまるところは「rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く」
問題
- 約数列挙
以下、解説やメモなど
ICPC 2016 国内予選 C. 竹の花
http://icpc.iisf.or.jp/past-icpc/domestic2016/problems/all_ja.html
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