内容別リスト/数学系 - 競技プログラミング用 知識集積所

---

四則演算系

• 剰余類環（C問題レベル）

答えが非常に大きくなるのでコレで割った余りだけ答えてください、という問題に答えるための知識。

素数系

• 素数判定（C問題レベル）

与えられた数が素数かどうか判定するアルゴリズム。試し割り法。

• エラトステネスの篩（D問題レベル）

n未満の素数を全て高速で列挙するアルゴリズム。
通常の方法でやれば計算回数がO(n√n)になるところ、O(n*loglogn)で済む。

• 素因数分解（C問題レベル）

与えられた数を素数の積に分解するアルゴリズム。
毎回O(n)かかるものと、前処理にO(n*loglogn)かかるがその後は毎回O(logn)ですむものがある。