数論

01 / 共通の仕組み

多くの問題は数論的な背骨を隠している。入力に潜む割り切り / 法 / 乗法の構造を見抜けば、 O(N) のループは O(log N) や O(N log log N) へと縮む。 古典的なサブパターンは 3 つ:ユークリッドの互除法での GCD、 指数を半分にしながらべき乗を取る冪剰余、合成数を一気にふるい落とす素数篩。

01 / 一文での本質
毎ステップで指数を半分にする。exp の 2 進表現が、 どの「平方項」が結果に乗算されるかを選ぶ —— O(log exp) で O(exp) を回避。
問題an mod M を計算a3n13M100
exp · 2 進ビット(下位 → 上位)10011213base · 各ステップで平方3baseresult · M を法とする累積積1result3^13 mod 100
3^13 mod 100 を計算。指数の 2 進表現 = 1011(下位ビットが先頭)。初期値 result = 1、base = 3 % 100。
ステップ
0 / 12
ビット i
—
base
3
result
1
0 / 12

02 / パターンの骨格

# (base^exp) mod M を O(log exp) で計算result ← 1base ← base % Mwhile exp > 0:if exp & 1: # exp の最下位ビットが 1result ← (result × base) % Mbase ← (base × base) % M # 平方exp ← exp >> 1 # 使ったビットを落とすreturn result

03 / このパターンを使うべき合図

"large modular exponent / aⁿ mod M"
典型的な用途。LC 50(pow(x, n) の浮動小数版 —— 同じ骨格、負指数の扱いを足すだけ)、 LC 372。aⁿ mod M で n がループには大きすぎる、と見たらこれ。
"modular multiplicative inverse via Fermat's little theorem"
法 p が素数のとき、a⁻¹ ≡ a^(p−2) (mod p)。 拡張ユークリッドを使わずに、冪剰余を 1 回呼ぶだけで逆元が手に入る —— 素数法での「割り算」の鍵(二項係数や数え上げで頻出)。
"matrix exponentiation"
同じ骨格で、× を行列積に置き換え、result を単位行列で初期化する。 これが O(k³ log N) で N 番目の Fibonacci や任意の線形漸化式の N 番目項を求める標準手順。
"super-pow / nested exponent"
LC 372。指数自体が巨大な桁配列 b = [b₀, b₁, …] のときは、a^b = (a^(b/10))^10 · a^(b mod 10) で再帰。 各層では ≤ 10 の小指数に対する冪剰余だけ。

04 / よくある落とし穴

i.
乗算後に % M を忘れる。
base * base はすでに [0, M²) の範囲にある。 すぐに % M しないと、数回の平方で 64 ビット整数を溢れる。 剰余は「あとでまとめて」ではなく、乗算が起きるその場で取る。
ii.
ビットが 0 でも result に乗算してしまう。
この技の核心は「1 のビットだけが寄与する」こと。 条件なしに result *= base としてしまうと、計算しているのは base^(反復回数) であり、まったくの別物。乗算は if exp & 1 でガードする。
iii.
exp == 0 を誤って特別扱いする。
result の初期値が 1 なので、exp == 0 ならループ本体は実行されず、 自然に 1 が返る —— これは 0⁰(本文脈では慣例的に 1)も含む。 「exp == 0 なら 0 を返す」ような余計なガードを足さない。

05 / LeetCode で練習

4 問。LC 50 は同じ骨格の浮動小数版、残りは指数が巨大でループ不可能な冪剰余の問題。

01Pow(x, n)— LC 50中級→02Super Pow— LC 372中級→03Count Good Numbers— LC 1922中級→04Count Collisions of Monkeys on a Polygon— LC 2550中級→

— / どれをいつ使うか

GCD / LCM
問題の核が割り切りであるときに使う — 公約数、互いに素か、既約分数、 a · b / gcd(a, b) から LCM を導出。 ユークリッドの恒等式 gcd(a, b) = gcd(b, a % b) は 1 ステップごとに幾何級数で減る。
ユークリッド · LC 1071 · LC 1979
冪剰余
巨大な n に対する aⁿ mod M や素数を法とする乗法逆元が必要なときに使う。 指数を毎ステップ半分にし、n のビット並びでどの平方項が乗算されるかが決まる。O(log n)。
指数の半減 · LC 50 · LC 372
素数篩
N 以下の素数(または最小素因子)を全て列挙するときに使う。 各素数 p の倍数を合成数として一気にマークする; 各合成数のマーク回数は償却 O(log log N)。
エラトステネス · LC 204 · LC 952