C2: Modular Inverse

解説

拡張ユークリッドの互除法は $ax + Ly = \mathrm{gcd}(a, L)$ を満たす整数の組 $(x, y)$ を求める古典アルゴリズムです。

今回 $a$ と $L$ は互いに素 ($\mathrm{gcd}(a, L) = 1$) なので、$ax + Ly = 1$ を満たす整数の組 $(x, y)$ を求めることができます。

$ax + Ly = 1 \Leftrightarrow ax = 1 - Ly$ について、両辺の $\bmod\ L$ を取ることで、$ax = 1 \bmod L$が成り立ちます。

よって $x = a^{-1} \bmod L$ が成り立ちます。

拡張ユークリッドの互除法を使うことで効率的に $x$ を求めることができます。

今回は $L$ が素数とは限らないため、フェルマーの小定理を使うことはできません。

解答例

解答例は以下の通りです。

# Extended Euclidean Algorithm
 
 
def extended_euclidean(a: int, b: int) -> tuple[int, int, int]:
    # when b == 0:
    if b == 0:
        return a, 1, 0
 
    # recursive step
    gcd, x1, y1 = extended_euclidean(b, a % b)
 
    # update x and y
    x = y1
    y = x1 - (a // b) * y1
 
    return gcd, x, y
 
 
def solve(a: int, L: int) -> int:
    _, x, _ = extended_euclidean(a, L)
 
    return x % L