結果
問題 | No.1287 えぬけー |
ユーザー |
![]() |
提出日時 | 2020-10-01 03:42:36 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,592 ms / 2,000 ms |
コード長 | 574 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-07 01:20:33 |
合計ジャッジ時間 | 7,721 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 5 |
ソースコード
# 拡張ユークリッド互除法 # ax + by = gcd(a, b) となる解 (x, y) の一例と gcd(a, b) を求める # 引数 (a, b) 返り値 (gcd(a, b), x, y) def egcd(a, b): if a == 0: return b, 0, 1 else: g, y, x = egcd(b % a, a) return g, x - (b // a) * y, y def solve(x, k): # a(mod-1) + b(-k) = 1 _, _, b = egcd(mod-1, -k) # a(mod-1) + b(-k) = -1 にして、 0 <= b < mod-1 にする b *= -1 b %= mod-1 n = pow(x, b, mod) return n mod = 10**9+7 t = int(input()) for _ in range(t): x, k = map(int, input().split()) print(solve(x, k))