Day 155-Q2 — Schönhage–Strassen法（NTTベース大整数乗算）

2026-09-16 赤色 Master / Phase 8+ ★★★★★★★★★ ブロック分割+NTT畳み込み+繰り上がり一括処理

問題

2つの非負整数 $A, B$ が10進数の文字列として与えられる。Schönhage–Strassen法の考え方——各数を固定サイズのブロック（基数 $B_{\text{block}}$ の桁）に分割し、ブロック列同士の畳み込みをNTTで高速に計算してから、まとめて繰り上がり（キャリー）を伝播させる——に従って、$A\times B$ を計算せよ。

素朴な筆算は $O(D^2)$（$D$=桁数）だが、この方式では畳み込み部分が $O(D\log D)$ になる。畳み込みの結果はブロックごとの「生の積和」であり、桁の範囲を超えて良い——だからこそ、繰り上がり処理を畳み込みの後で一括して行うのが本手法の核心である。

入力形式

A
B

制約

$A,B$は10進数表記(不要な先頭0なし)
$1\le |A|,|B|\le 10^6$（桁数）
$A=0$または$B=0$なら`0`の1文字

入出力例

入力例1

123456789
987654321

出力例1

121932631112635269

概念図：ブロック畳み込み+繰り上がり（1234×5678, 基数100の例）

A=1234 (ブロック[34,12]) × B=5678 (ブロック[78,56]) a0=34 a1=12 b0=78 b1=56 c0=34×78=2652 34×56=1904↘ ↙12×78=936 c2=12×56=672 対角線ごとに合計: c0=2652, c1=1904+936=2840, c2=672 繰り上げ(base100)後 → 7,00,66,52 → 7006652 (実測一致)

ヒント（段階的開示）

ヒント1（方向性）

筆算で2つの $D$ 桁の数を掛けると $O(D^2)$ かかる。これは「2つの多項式（各桁を係数とみなす）の積を求める」操作と本質的に同じ形をしている。多項式の積が畳み込みで高速化できるなら、大整数の乗算も同じ枠組みで高速化できるはず、という方向で考える。

ヒント2（アプローチ）

$A$の桁列を多項式 $A(x)=\sum a_i x^i$ とみなし、$B(x)$も同様に作る。積の「係数列」は畳み込み $c_k=\sum_{i+j=k}a_i b_j$ で計算できる。畳み込みの結果 $c_k$ は1桁の範囲を超える——これは異常ではなく、想定通りの中間状態である。最後に「桁上げ」をまとめて処理して初めて普通の10進数の形に整える。

ヒント3（誘導） 
# 1. A,B を基数10^k(kは4など)でブロック分割し配列a,bを作る
# 2. a,b を畳み込む(NTT化する前提。今回は素朴なO(len(a)*len(b))でも可)
# 3. carry, digit = divmod(c_i + carry, 10**k) を下位ブロックから繰り返す
# 4. ブロック列を文字列に変換(先頭以外はk桁0埋め)

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    A_str, B_str = data[0], data[1]

    if A_str == "0" or B_str == "0":
        print(0)
        return

    K = 4  # ブロックサイズ（10進4桁 = 基数10000）
    BASE = 10 ** K

    def to_blocks(s):
        blocks = []
        n = len(s)
        i = n
        while i > 0:
            j = max(0, i - K)
            blocks.append(int(s[j:i]))
            i = j
        return blocks

    a = to_blocks(A_str)
    b = to_blocks(B_str)

    # 畳み込み（O(len(a)*len(b))の素朴実装。NTT化する場合はここを2べき長NTTに置き換える）
    conv = [0] * (len(a) + len(b) - 1)
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        for j, bj in enumerate(b):
            conv[i + j] += ai * bj

    # 繰り上がり伝播（畳み込み後にまとめて行うのが本手法の核心）
    carry = 0
    digits = []
    for c in conv:
        c += carry
        digits.append(c % BASE)
        carry = c // BASE
    while carry:
        digits.append(carry % BASE)
        carry //= BASE

    while len(digits) > 1 and digits[-1] == 0:
        digits.pop()

    parts = [str(digits[-1])]
    for d in reversed(digits[:-1]):
        parts.append(str(d).zfill(K))

    print("".join(parts))

solve()

Step-by-Step 解説

1多項式の積として見る
$A=1234$ を $A(x)=1x^3+2x^2+3x+4$ とみなせる。$A\times B$ の10進表記は $A(x)B(x)$ を計算後 $x=10$ を代入し桁上げを処理することと同じ。畳み込みとキャリー処理を分離するのが設計判断。
2実測トレース（基数100, 1234×5678）
ブロック: A=[34,12], B=[78,56]。生の畳み込み: c0=34×78=2652, c1=34×56+12×78=2840, c2=12×56=672。繰り上げ伝播: c0→digit52,carry26; c1+26=2866→digit66,carry28; c2+28=700→digit00,carry7。結果ブロック[52,66,00,7]→"7006652"。実際に$1234\times5678=7006652$と完全一致（本ファイル作成時にPythonで実測）。
3ブロックサイズKの選び方
畳み込み1要素の最大値はおよそ$(10^K-1)^2\times\min(|a|,|b|)$。使用する数値型の安全範囲に収まるようKを選ぶ。Kが大きいほど畳み込み長は減るが1要素の値は大きくなるトレードオフがある。
4なぜ「後でまとめて繰り上げる」のが速いか
筆算のように1桁ごとに繰り上げると繰り上がり処理と積の計算が絡み合い並列性を活かせない。畳み込みを先に全部終え、繰り上がりだけを線形時間$O(D/K)$で後処理することで全体を$O(D\log D)$に保てる。

よくあるミス

ミス原因正しい書き方
畳み込み結果をそのまま桁として出力畳み込み1要素が基数を超えることを忘れる必ず繰り上がり伝播(divmod)を畳み込みの後に通す
ブロック分割の順序を上位からにする配列インデックスと桁の重みの対応がずれる下位ブロックを配列の先頭(インデックス0)にする
出力時に先頭ブロック以外を0埋めし忘れるブロック文字列化のzfill漏れ最上位ブロックのみzfillなし、それ以外はzfill(K)
A=0またはB=0を素通りさせる特殊ケースの分岐漏れ先に"0"判定して0を出力する

次のステップ

  • 発展: NTT-friendlyでないモジュラスでの畳み込み（3素数CRT合成や複素FFT）を実装し、丸め誤差対策のブロックサイズのトレードオフを実測する。
  • 次回予告: Floyd's Cycle Detection + Brent's Algorithm（サイクル検出）

自己評価

自分の回答

気づき・メモ