競技プログラミングにおけるエラトステネスの篩・区間篩・調和級数計算量問題

uwiさんの最強まとめ

エラトステネスの篩

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

区間篩

• 「R<=10^12, R-L<=10^6という制約がヒント」
• [L,R]の区間の素数判定をする手法である
• [L,R]の区間の素因数分解もできる

調和級数的計算量

• エラトステネスの篩がO(NlogN)で計算できるというような計算量の考え方を調和級数的計算量みたいに表現したりもする
• つまるところは「rep(i,1,N) for(j=i;j<=N;j+=i) というループ構造はO(NlogN)で行えるという所を応用して問題を解く」

問題

• 素数列挙
  • ACPC 素数 解説
  • yukicoder No.843 Triple Primes 解説

• 約数列挙
  • HUPC2019B 自身の 2 倍 解説

• エラトステネスの篩的計算量（調和級数計算量）で解ける
  • ICPC 2016 国内予選 C. 竹の花
  • Codeforces 376 F. Video Cards
  • SRM 703 Mid DAGConstruction
  • Educational Codeforces Round 20 F. Coprime Subsequences
  • Educational codeforces Round 14 F. Couple Cover
  • Maximum Gcd and Sum
  • yukicoder No.555 世界史のレポート 解説
  • CSA66 Counting Quacks 解説
  • AC チーム分け 解説
  • HUPC2019 Day2 F MOD Rush 解説
• 区間篩
  • CC Chef and Divisor Tree 解説
  • JAG Prime-Factor Prime 解説

以下、解説やメモなど

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