結果
問題 | No.3133 法B逆元 |
ユーザー |
|
提出日時 | 2025-05-02 21:44:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 436 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 12,032 KB |
実行使用メモリ | 10,368 KB |
最終ジャッジ日時 | 2025-05-02 21:44:45 |
合計ジャッジ時間 | 1,646 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys import math def extgcd(a:int, b:int) -> tuple[int,int,int]: if b==0: return a,1,0 g,x1,y1=extgcd(b, a%b) x=y1 y=x1-(a//b)*y1 return g,x,y def main(): data = sys.stdin.read().split() if len(data)<2: return n,b=map(int, data[:2]) if math.gcd(n, b)!=1: print("NaN") return g,x,y=extgcd(n,b) x%=b print(x) if __name__ == "__main__": main()