算術の基本定理 - 素因数分解の理論と実装
算術の基本定理
素数と素因数の基礎概念
算術の基本定理を理解するにあたり、まず基本となる用語を整理しておこう。素数とは、2以上の自然数のうち、1とその数自身以外では割り切れない数を指す。代表的な素数としては2、3、5、7、11などが挙げられる。一方、素因数とは、ある整数を構成する素数のことを意味する。例えば、12という数は2×2×3という積で表わされるが、この ...
6月28日 20:09 投稿
オイラーのトーシェント関数と線形ふるい法による計算
例えば、6のオイラーのトーシェント関数を求める場合：6=2×3なので、そのトーシェント関数は6×(2-1)/2×(3-1)/3となります。
原理：1~NのうちNと互いに素な数の個数は、NからNと互いに素でない数を引いたものに等しくなります。Nと互いに素でない数はNの因数の倍数によってふるい落とされますが、一部の数は複数の因数によって複数回ふるい落とされるため、因数の積の倍数を ...
6月15日 22:32 投稿
Miller-Rabin 素数判定と Pollard-Rho 素因数分解
Miller-Rabin 素数判定
Miller-Rabin 法は、フェルマーの小定理と二次探査定理を組み合わせた確率的素数判定アルゴリズムです。以下の手順で動作します。
偶数および 0, 1, 2 は事前に判定します。
判定対象の奇数 n に対し、n - 1 = 2s × d（d は奇数）と分解します。
小さな素数 a を基底として選び、ad mod n を計算し、その後 s 回の平方と二次探査を行います。
最 ...
5月28日 04:02 投稿
競技プログラミングにおける探索・数論・木構造アルゴリズムの実装技法
行選択による列制約の充足判定
グリッド状のデータに対し、行の削除操作を制限回数内で行った後、残存する列の要件数が指定値以下に収まるかを検証する問題である。行数が比較的小さいため、深さ優先探索を用いて行の採用・不採用のパターンを網羅する。各探索ノードでは、未削除行に含まれる列インデックスを集合に記録し、重複を除いた後のサイズが閾値を超えないか判定 ...
5月26日 19:47 投稿