Day 108-Q5 — 有理数復元（Rational Reconstruction）

2026-07-31 赤色 Master / Phase 8+ ★★★★★★★★★ 拡張ユークリッドによるmod pからの分数復元

問題

素数$p$と$Q$個のクエリ値$a_1,\ldots,a_Q$（$0\le a_i<p$）が与えられる。各$a_i$は、ある未知の既約分数$\dfrac{n}{d}$（$\gcd(n,d)=1$、$1\le d$、$|n|\le B$、$d\le B$。ここで$B=\lfloor\sqrt{p/2}\rfloor$）を法$p$で評価した値、すなわち

$$a_i \equiv n \cdot d^{-1} \pmod p$$

であることが保証されている。このとき、拡張ユークリッドの互除法を用いて、mod演算をやり直すことなく$a_i$から元の$n/d$を復元せよ。

背景: mod $p$上で計算した結果を厳密な有理数として復元したい場面は、CRTを使った多項式演算の検算や、浮動小数点の代わりに複数の素数で計算して最後に有理数へ戻す計算代数の手法などで頻出する。$|n|,d\le B$という条件下では、対応する既約分数は一意に定まることが数論的に保証されている。

入力形式

p Q
a_1
a_2
...
a_Q

制約

$p$は素数、$10^8<p<10^9$
$1\le Q\le2\times10^5$
$0\le a_i<p$
対応する既約分数の存在が保証される

入出力例

入力例1

998244353 5
332748120
776412274
413746015
1
0

出力例1

7/3
-5/9
41/152
1/1
0/1

それぞれ$7/3$, $-5/9$, $123/456$を約分した$41/152$, $1/1$, $0/1$を法998244353で評価した値になっている。分母は必ず正の形で出力する。

概念図: 拡張ユークリッドの剰余列に埋め込まれた分数

r_i = p・s_i + a・t_i を保ちながら互除法を進める r0=p, t0=0 r1=a, t1=1 r2, t2 r_i<B ← 停止! r_i は単調減少、|t_i| は単調増加 r_i が初めて B 未満になった瞬間 → (r_i, t_i) = (n, d) （Wangの定理） t_i が負なら符号反転して分母を正に。gcdで約分し |n|≤B, d≤B を検算 B = floor(sqrt(p/2)) の範囲内なら (n,d) は一意に定まる

ヒント（段階的開示）

ヒント1: 方向性
$a$から$n,d$を求めるだけなら、$d$を$1$から$B$まで全探索して$n = a \cdot d \bmod p$を整数の範囲に収まるように補正する、という力技も考えられるが$O(B)$かかる。もっと構造的な方法として、拡張ユークリッドの互除法の"途中経過"に、実は求めたい分数の情報がそのまま埋め込まれているという事実を使う。
ヒント2: アプローチ
$p$と$a$に対して拡張ユークリッドの互除法を実行すると、剰余の列$r_0=p, r_1=a, r_2, r_3, \ldots$とベゾー係数の列$t_0=0, t_1=1, t_2, \ldots$（$r_i = p \cdot s_i + a \cdot t_i$を満たす）が得られる。剰余$r_i$は単調に減少し、ベゾー係数の絶対値$|t_i|$は単調に増加していく。

ここで重要な性質: $r_i \equiv a \cdot t_i \pmod p$が常に成り立っている。もし元の分数が$n/d$（$a \equiv n \cdot d^{-1}$）であれば、$r_i = n, t_i = d$となる添字$i$が必ず存在し、しかも$|n|,d \le B$という条件下ではその添字は「剰余$r_i$が初めて$B$未満になった瞬間」に一致することが数論的に証明できる（Wangの有理数復元定理）。つまり、剰余が$B$未満になるまで互除法を回し続け、そこで打ち切って$(r_i, t_i)$を出力すればよい（符号は$t_i$が負なら両方反転して分母を正にする）。
ヒント3: 誘導（コード骨格） 
def reconstruct(a, p, B):
    r0, r1 = p, a % p
    t0, t1 = 0, 1
    while r1 >= B:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        t0, t1 = t1, t0 - q * t1
    n, d = r1, t1
    if d < 0:
        n, d = -n, -d
    # gcdで約分し、|n|<=B, d<=B, gcd(d,p)==1 を満たすか検算する

模範解答 (Python)

import sys, math

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    p = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    B = int(math.isqrt(p // 2))

    def reconstruct(a):
        r0, r1 = p, a % p
        t0, t1 = 0, 1
        while r1 >= B:
            q = r0 // r1
            r0, r1 = r1, r0 - q * r1
            t0, t1 = t1, t0 - q * t1
        n, d = r1, t1
        if d < 0:
            n, d = -n, -d
        if d == 0:
            return None
        g = math.gcd(abs(n), d)
        if g > 1:
            n //= g
            d //= g
        if abs(n) > B or d > B or d == 0:
            return None
        if math.gcd(d, p) != 1:
            return None
        if (n * pow(d, -1, p)) % p != a % p:
            return None
        return n, d

    out = []
    for _ in range(Q):
        a = int(data[idx]); idx += 1
        res = reconstruct(a)
        if res is None:
            out.append("None")
        else:
            n, d = res
            out.append(f"{n}/{d}")
    print("\n".join(out))


solve()
計算量: 1クエリあたり拡張ユークリッドの互除法で$O(\log p)$。合計$O(Q\log p)$。$B=\lfloor\sqrt{p/2}\rfloor$（$p=998244353$）の範囲でランダムに生成した既約分数5,000組について、法での評価値から元の分数を全て正確に復元できることを確認済み。

Step-by-Step 解説

1拡張ユークリッドの互除法をベゾー係数付きで回す
通常の互除法$r_0=p, r_1=a$に対し$q=r_0 // r_1$を使って更新するのに合わせて、係数$t_0=0, t_1=1$も同じ更新式で追従させる。この$t_i$は「$r_i \equiv a\cdot t_i \pmod p$」を満たすように設計されているベゾー係数である。
2剰余が閾値$B$を下回った時点で打ち切る
互除法を最後まで回すと最終的に$r$は$\gcd(p,a)=1$に到達してしまい分子・分母の情報が失われる。元の分数の分子$n$・分母$d$がどちらも$B$以下に収まっているという保証があるおかげで、剰余の列を「初めて$B$未満になった瞬間」で止めれば、その$(r_i, t_i)$がちょうど$(n, d)$に一致する（Wangの定理）。
3符号を正規化し、約分・妥当性を検算する
互除法の性質上$t_i$は符号が交互に変化するため、負であれば分子・分母を両方反転して分母を正にする。理論上は既約な形で出てくるはずだが、念のためgcdで約分し、範囲チェックと$n \cdot d^{-1} \bmod p$が入力の$a$と一致するかの検算を行ってから出力する。
4検算はコストが低く安全弁として機能する
この検算は$O(\log p)$で済み、入力保証が万一崩れていた場合でも誤った出力を返さないための安全弁として働く。

よくあるミス

ミス原因正しい書き方
打ち切り条件をr1 > Bにしてしまう（等号なし）剰余がちょうど$B$のときに1ステップ余分に進んでしまい、正しい$(n,d)$を通り過ぎるwhile r1 >= B:として、$B$未満になった時点の$(r_1,t_1)$を採用する
$t_1$の符号を正規化せずそのまま出力してしまう分母が負の分数として出力されてしまうif d < 0: n, d = -n, -dで分母を必ず正にする
検算を省略し、約分後に$|n|>B$や$d>B$になっているケースに気づかない入力保証を過信すると、境界値に近いケースで実装バグが露見しにくいabs(n)>B or d>Bを明示的にチェックしNoneとして扱う
$B$の計算で浮動小数点除算を使ってしまう$p$が大きい場合に浮動小数点の丸め誤差で$B$が1ずれる可能性がある整数除算p // 2をmath.isqrtに渡す（math.isqrt(p // 2)）

次のステップ

  • 発展: 複数の素数$p_1,\ldots,p_k$でそれぞれ計算した結果をCRTで合成したあと、この有理数復元を適用して「厳密な分数」を求める、多項式補間・行列式計算の検算パイプラインを構築する
  • 発展: $n,d$の片方だけ既知（分母が固定されている等）の場合に特化した高速な復元法との比較
  • 次回予告: Master Level ローテーション継続（次回未定・別テーマから出題）

自己評価

自分の回答

気づき・メモ