C2: Modular Inverse

問題文

互いに素な正の整数 $a$, $L$ が入力として与えられる。

$a^{-1}\ \text{mod}\ L$ を計算せよ。

ただし、$a^{-1}$ は $a$ の逆元であり、$a \cdot a^{-1} \equiv 1\ (\text{mod}\ L)$ を満たす整数として定義される。

制約

• $1 \leq a < L \leq 2^{1024}$
• 結果は整数型の返り値として返すこと。
• 提出されるコードは次のフォーマットにしたがうこと

def solve(a: int, L: int) -> int:
    result: int = 0
    # Write your code here:
 
    return result

ヒント