Day 084-Q2 — 区間 GCD クエリ（Sparse Table / 冪等半群 $O(N \log N)$ 前処理・$O(1)$ クエリ）

2026-07-07 赤色 Master / Phase 8+ ★★★★★★★★★ Sparse Table・GCD・冪等半群

問題

長さ $N$ の整数列 $A$ が与えられる。$Q$ 個のクエリ $(l_i, r_i)$ が与えられ、各クエリで $\gcd(A[l_i], A[l_i+1], \ldots, A[r_i])$ を答えよ。

$\gcd$ は冪等（$\gcd(a,a)=a$）かつ結合的な半群演算であるため、Sparse Table による $O(1)$ クエリを実現できる（$O(N \log N)$ 前処理）。

制約

パラメータ範囲備考
$N$$\le 5 \times 10^5$配列長
$Q$$\le 10^6$クエリ数
$A_i$$1 \le A_i \le 10^9$配列要素
$l_i, r_i$$1 \le l_i \le r_i \le N$1-indexed

入出力例

入力例1

6 5
12 8 6 4 9 3
1 3
2 5
1 6
3 6
4 6

出力例1

2
1
1
1
1

概念図: Sparse Table の構造と $O(1)$ クエリ

Sparse Table for GCD — A = [12, 8, 6, 4, 9, 3] k\i i=0 i=1 i=2 i=3 i=4 i=5 意味: gcd(A[i..i+2^k-1]) k=0 12 8 6 4 9 3 k=1 4 2 2 1 各2要素のgcd k=2 2 1 各4要素のgcd クエリ gcd(A[1..5]) (0-indexed: [0..4]) の O(1) 処理 長さ = 5, k = floor(log2(5)) = 2, 2^k = 4 区間1: [0, 3] → table[2][0] = 2 区間2: [1, 4] → table[2][1] = 1 答え = gcd(2, 1) = 1 ← 重なりがあっても冪等性で OK ※ 区間 [0,3] と [1,4] は長さ4で区間[0,4]を覆う（重複可）

ヒント

ヒント1（方向性）

GCD は冪等半群（$\gcd(x,x)=x$）を満たすため、Sparse Table が適用できる。Sparse Table では table[k][i] = gcd(A[i..i+2^k-1]) を前計算し、クエリ $[l,r]$ に対して $k = \lfloor\log_2(r-l+1)\rfloor$ として gcd(table[k][l], table[k][r-2^k+1]) を返す（重なりがあってもよい）。

ヒント2（アプローチ）

前処理の漸化式：$$\text{table}[k][i] = \gcd(\text{table}[k-1][i],\ \text{table}[k-1][i + 2^{k-1}])$$

クエリ応答：$$\gcd(A[l..r]) = \gcd(\text{table}[k][l-1],\ \text{table}[k][r-2^k])$$（0-indexed で $k = \lfloor\log_2(r-l+1)\rfloor$）

ヒント3（ほぼ答え） 
import math
LOG = 20

def build_sparse_table(A):
    n = len(A)
    table = [A[:]]
    for k in range(1, LOG):
        prev = table[k-1]
        cur = [math.gcd(prev[i], prev[i + (1 << (k-1))])
               if i + (1 << k) - 1 < n else prev[i]
               for i in range(n)]
        table.append(cur)
    return table

def query(table, l, r):  # 0-indexed [l, r]
    length = r - l + 1
    k = length.bit_length() - 1
    return math.gcd(table[k][l], table[k][r - (1 << k) + 1])

模範解答

import sys
import math
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))

    LOG = N.bit_length() + 1
    table = [A[:]]
    for k in range(1, LOG):
        half = 1 << (k - 1)
        prev = table[k - 1]
        cur = []
        for i in range(N):
            j = i + half
            cur.append(math.gcd(prev[i], prev[j]) if j < N else prev[i])
        table.append(cur)

    log2 = [0] * (N + 1)
    for i in range(2, N + 1):
        log2[i] = log2[i >> 1] + 1

    def query(l, r):  # 1-indexed
        l -= 1; r -= 1
        length = r - l + 1
        k = log2[length]
        return math.gcd(table[k][l], table[k][r - (1 << k) + 1])

    out = []
    for _ in range(Q):
        l, r = map(int, input().split())
        out.append(query(l, r))

    sys.stdout.write('\n'.join(map(str, out)) + '\n')

solve()

Step-by-Step 解説

Step 1: 冪等半群と Sparse Table

演算冪等性Sparse Table 適用
GCD$\gcd(a,a)=a$ ✓✓ $O(1)$ クエリ
最大値$\max(a,a)=a$ ✓✓ $O(1)$ クエリ
最小値$\min(a,a)=a$ ✓✓ $O(1)$ クエリ
和$a+a \ne a$ ✗✗ BIT/SegTree 使用

Step 2: $O(1)$ クエリの仕組み

区間 $[l,r]$ の長さ $k = \lfloor\log_2(r-l+1)\rfloor$ として、長さ $2^k$ の2区間で覆う。重なりを許しても冪等性により正しい答えが得られる。

k = log2[r - l + 1]
ans = gcd(table[k][l], table[k][r - (1 << k) + 1])

Step 3: 計算量

操作計算量
前処理$O(N \log N \cdot \log C)$
クエリ$O(\log C)$（GCD のコスト）
空間$O(N \log N)$

よくあるミス

ミス原因正しい書き方
log2 を毎回 math.log2() で計算浮動小数誤差・速度問題bit_length() - 1 か前計算テーブル
テーブル範囲外アクセスi + 2^(k-1) >= N のとき範囲チェックして前の値をコピー
1-indexed と 0-indexed の混在off-by-one バグクエリ関数内で変換を統一

次のステップ

  • 発展問題: 区間 GCD クエリ + 区間更新（セグメント木が必要）
  • 発展問題: 左端固定で右端を伸ばした際の GCD 変化区間列挙 $O(N \log N \log C)$

自己評価

理解度: / /

自分の回答:

気づき・メモ: