結果

問題 No.3133 法B逆元
ユーザー かえる☔
提出日時 2025-05-02 21:29:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 483 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 52,096 KB
最終ジャッジ日時 2025-05-02 21:29:08
合計ジャッジ時間 1,717 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

def extend_euclid(a, b):
    def inner(a, b, ae, be):
        if b == 0:
            if a == 1:
                return ae
            else:
                return None
        new_be = [0, 0]
        new_be[0] = ae[0] - a // b * be[0]
        new_be[1] = ae[1] - a // b * be[1]
        return inner(b, a%b, be, tuple(new_be))
    return inner(a, b, (1, 0), (0, 1))

N, B = map(int, input().split())
ans = extend_euclid(N, B)
if ans is None:
    print("NaN")
else:
    print(ans[0]%B)
0