カテゴリー: アルゴリズム

中国のブログ[1]に面白いアルゴリズムがあったので…

\(p\) を奇素数として \(\mathbb{F}_p\) における平方根を \(O(\log p)\) で求める Cipolla のアルゴリズムを解説する。フロベニウス写像との関連を説明して、平方根以外の場合についても拡張する。

\(n\) 頂点重み付き有向グラフ \(G\) が与えられたとする。このとき、全頂点間の最短道の長さを \(O(n^3)\) で計算する Floyd-Warshall（フロイド・ワーシャル）のアルゴリズムを解説する。

この記事ではラベル付き木を全単射な方法で数列に変換する、Prüfer コード（Prüfer 列）と呼ばれるテクニックを解説する。Prüfer コードを使えば、ラベル付き木を数えやすい対象に変換することができ、木の数え上げに威力を発揮する。

FFTの転置写像から時間間引きと周波数間引きのアルゴリズムを相互に導出する。

拡張ユークリッドの互除法の実装を短くするテクニックを紹介します。

Noga Alon の二部（多重）グラフの辺彩色のアルゴリズムを解説します。計算量は辺数を \(E\) として \(O(E \log E)\) です。

\(\bmod p\) における平方根を求める Tonelli-Shanks のアルゴリズムを解説します。他の冪根への応用も見据えました。

素数を線形時間で列挙する篩を扱います。付随して列挙される最小素因数を用いて冪数を効率的に列挙する方法も解説しました。

level ancestor を前計算 \(O(N)\) 、クエリ当たり \(O(1)\) で計算するアルゴリズムを解説します。色々なテクニックがぎゅっと詰まってます。