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 投稿