数論の基礎と応用
因数に関する考察
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 投稿
min25筛と洲閣筛
min25筛
ある積性関数 f(x) が与えられ、f(p) が素数 p に関する多項式で、かつ f(pk) が高速に計算できる場合、sumi=1n f(i) を求める。
例：n = 1010 に対して sumi=1n σ0(ik) を求める。
ステップ1：素数の積性関数の前処理和
1 から n までの素数の個数を求める。
f(n, m) を、2 から n までの数のうち、素数であるか、または最小の素因数が p1, ..., pm (pi は i 番 ...
6月1日 21:05 投稿