数論の基礎と応用
因数に関する考察
1からnまでのすべての数の因数の総数はO(n log n)である。
1からnまでの素数の個数はO(n / log n)である。
伯トラン・チェビシェフの定理：n ≥ 1のとき、nと2nの間に少なくとも1つの素数がある。
直角三角形の辺の長さの一般式：a = w * 2uv, b = w * (u^2 - v^2), c = w * (u^2 + v^2)、ここでu, v, wは正の整数。
問題
Common Divisors: a_1, a_2, ...
6月22日 20:48 投稿
アルゴリズムとデータ構造8 - 線形篩による一般乗法関数の計算
概要
競技プログラミングの問題を解く中で、線形篩を用いた一般乗法関数の計算方法を学んだので、その説明を行う。
前提知識
乗法的関数：任意の互いに素な整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
完全乗法的関数：任意の整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
線形篩：O(n)でn以下の素数を列挙するアルゴリズム。
適用範囲
任意の素数pに対して、f(p)およ ...
6月10日 19:05 投稿