木の頂点 $u$, $v$ について最小共通先祖 (LCA) を計算するシンプルなアルゴリズムを紹介します．複数の頂点の組に対して LCA を求めるのであれば，木を前処理をしてクエリあたり $O(\log n)$ なり $O(1)$ で求めるのが定石ですが，ここではそうでなく，線形…

正整数 $ m $ と整数 $ a \in [0, m) $ について $ x^2 = a \mod m $ の解を求めます． 方針 $ m = p_1^{e_1} \cdots p_k^{e_k} $ と素因数分解し，各素数べきについて $ x^2 = a \mod p_i^{e_i} $ を解いて，中国剰余定理を用いて解を構成します． 素因数分…

Sorensen's Incremental Sieve は素数を順番に列挙するアルゴリズムです．このアルゴリズムは incremental, compact という 2 つの性質をもっています．incremental というのは $n$ までの素数を列挙したとき $n+1$ に対する処理が高速（$ t(n) $ 回の算術演…

概要 整数ベクトル $B := (b_1, \ldots, b_m) \in \mathbb{Z}^{m \times n} $ が与えられたとき，これらの整数線型結合で作られる集合 $L(B) := \{ x_1 b_1 + \ldots + x_m b_m : x_1, \ldots, x_m \in \mathbb{Z} \} \subseteq \mathbb{Z}^n $ を lattice …