合同算術の基本性質
整数 a と b が法 m において合同であるとは、m が (a - b) を割り切ることを意味し、これを \( a \equiv b \pmod{m} \) と表記する。この関係は以下の代数的性質を持つ：
- 加法不変性: \( a \equiv b \pmod{m} \) ならば、任意の整数 c に対して \( a + c \equiv b + c \pmod{m} \) が成り立つ。
- 乗法不変性: 同様に、\( a \cdot c \equiv b \cdot c \pmod{m} \) および、c と d も合同であれば \( a \cdot c \equiv b \cdot d \pmod{m} \) が成立する。
- 冪乗不変性: \( a \equiv b \pmod{m} \) ならば、任意の非負整数 n に対して \( a^n \equiv b^n \pmod{m} \) が成り立つ。
除法に関しては直接的な逆元は存在しないが、gcd(c, m) = 1 の場合、\( a \cdot c \equiv b \cdot c \pmod{m} \) から \( a \equiv b \pmod{m} \) を導くことができる。
素数とその判定
素数は1より大きい自然数で、1と自分自身以外の正の約数を持たない数である。素因数分解の一意性（算術の基本定理）により、任意の合成数は一意な素数の積として表現できる。効率的な素数判定には以下のようなアルゴリズムがある：
エラトステネスの篩
指定された上限 N までのすべての素数を列挙する古典的なアルゴリズム。初期状態では2以上のすべての数を素数と仮定し、最小の未処理の素数 p について、\( p^2 \) から始まる p の倍数を順次除外していく。
void sieve(int n, vector<bool>& is_prime) {
is_prime.assign(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
}
線形篩（オイラーの篩）
各合成数をその最小の素因数によって一度だけ除外することで、計算量を O(N) に抑える高度な手法。
void linear_sieve(int n, vector<int>& primes) {
vector<bool> composite(n + 1, false);
for (int i = 2; i <= n; ++i) {
if (!composite[i]) primes.push_back(i);
for (int prime : primes) {
if (i * prime > n) break;
composite[i * prime] = true;
if (i % prime == 0) break; // 最小素因数でストップ
}
}
}
オイラーのφ関数
オイラーのトーシェント関数 φ(n) は、1 から n までの整数のうち n と互いに素なものの個数を表す。n の素因数分解が \( n = p_1^{k_1} p_2^{k_2} ... p_r^{k_r} \) のとき、次の公式が成り立つ：
\[ \phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)...\left(1 - \frac{1}{p_r}\right) \]
φ 関数は乗法的関数であり、互いに素な a と b に対して \( \phi(a \cdot b) = \phi(a) \cdot \phi(b) \) が成り立つ。単一の値を求める場合は試除法を用い、複数の値を同時に求める場合は線形篩と組み合わせる。
拡張ユークリッドの互除法
最大公約数 gcd(a, b) を計算すると同時に、ベズーの等式 \( a \cdot x + b \cdot y = \text{gcd}(a, b) \) を満たす整数解 (x, y) を求めるアルゴリズム。これはモジュラー逆元の計算や一次合同方程式の求解に不可欠である。
int extended_gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int g = extended_gcd(b, a % b, y, x);
y -= (a / b) * x;
return g;
}
モジュラー逆元
ある整数 a が法 m において逆元 \( a^{-1} \) を持つのは、gcd(a, m) = 1 のとき（つまり a と m が互いに素なとき）に限られる。主な計算方法は以下の通り：
- フェルマーの小定理（m が素数の場合）: \( a^{-1} \equiv a^{m-2} \pmod{m} \)。繰り返し二乗法で高速に計算可能。
- 拡張ユークリッド法: 上記のアルゴリズムを使って \( a \cdot x + m \cdot y = 1 \) を解き、その x を m を法として正規化する。
- 線形再帰法（m が素数の場合）: \( \text{inv}[i] = (m - \lfloor m/i \rfloor) \cdot \text{inv}[m \bmod i] \bmod m \) という漸化式で、1 から n までの逆元をまとめて O(n) で計算できる。
中国剰余定理 (CRT)
互いに素な法 m₁, m₂, ..., mₖ に関する合同方程式系
\[ \begin{cases} x \equiv r_1 \pmod{m_1} \\ x \equiv r_2 \pmod{m_2} \\ ... \\ x \equiv r_k \pmod{m_k} \end{cases} \]
の解 x を求める定理。解は \( M = m_1 \cdot m_2 \cdot ... \cdot m_k \) を法として一意に存在し、その最小非負解は次式で与えられる：
\[ x = \left( \sum_{i=1}^{k} r_i \cdot c_i \cdot c_i^{-1} \right) \bmod M \quad \text{ただし } c_i = M / m_i \]
ここで \( c_i^{-1} \) は \( c_i \) の \( m_i \) を法とする逆元である。法が互いに素でない一般の場合には、逐次的に2つの合同式を統合する「拡張CRT」を用いる。
ルーカスの定理
非常に大きな n, m に対して、素数 p を法とする二項係数 \( C(n, m) \bmod p \) を計算するための定理。n と m を p 進数で展開したとき、
\[ C(n, m) \equiv \prod C(n_i, m_i) \pmod{p} \]
が成り立つ。右辺の各 \( C(n_i, m_i) \) は通常の方法で計算でき、全体は再帰的に求めることができる。p が合成数の場合には、「拡張ルーカスの定理」により、p を素因数べき \( p_i^{k_i} \) に分解し、それぞれの法で合同式を立ててから中国剰余定理で統合する。
カタラン数
多くの組合せ問題に現れる数列。第 n 項 \( C_n \) は、次のように定義される：
\[ C_n = \frac{1}{n+1}C(2n, n) = C(2n, n) - C(2n, n-1) \]
典型的な応用例として、n 個の要素のスタックへの押し出し手順の数、n 組の括弧の正しい並べ方の数、n+1 個の葉を持つ完全二分木の構造数などがある。
BSGSアルゴリズム
離散対数問題、すなわち \( a^x \equiv b \pmod{p} \) を満たす x を求める問題を、O(√p) 時間で解くアルゴリズム。x を \( x = i \cdot m - j \) （ただし \( m = \lceil \sqrt{p} \rceil \), \( 0 \leq j < m \)）と置き換えることで、\( (a^m)^i \equiv b \cdot a^j \pmod{p} \) という形に変形する。まず j を全探索して右辺の値と j をハッシュマップに格納し、次に i を増やしながら左辺の値がマップに存在するかを調べる。