結果
問題 | No.3022 一元一次式 mod 1000000000 |
ユーザー |
|
提出日時 | 2025-02-14 21:31:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 473 ms / 2,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 12,032 KB |
実行使用メモリ | 31,660 KB |
最終ジャッジ日時 | 2025-02-17 12:56:14 |
合計ジャッジ時間 | 2,857 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys import math def extended_gcd(a, b): # (g, x, y) となるように、g = gcd(a,b) and a*x + b*y = g if b == 0: return (a, 1, 0) else: g, x1, y1 = extended_gcd(b, a % b) return (g, y1, x1 - (a // b) * y1) def modinv(a, m): # 拡張ユークリッド法により a の m における逆元を求める. g, x, _ = extended_gcd(a, m) if g != 1: # a と m が互いに素でないときは逆元は存在しない return None return x % m def main(): data = sys.stdin.read().strip().split() if not data: return t = int(data[0]) mod = 10**9 ans = [] index = 1 for _ in range(t): N = int(data[index]); M = int(data[index+1]) index += 2 d = math.gcd(N, mod) # 解が存在する条件: d が M を割る if M % d != 0: ans.append("-1") continue # 両辺 d で割る a = N // d m_prime = mod // d # b' = -M/d (b' は負になるかもしれないが、後で mod m_prime で正の代表元に変換する) b_prime = -M // d inv_a = modinv(a, m_prime) # 解 k ≡ b_prime * inv_a (mod m_prime) k0 = (b_prime * inv_a) % m_prime # k=0 は正整数ではない if k0 == 0: k0 = m_prime ans.append(str(k0)) sys.stdout.write("\n".join(ans) + "\n") if __name__ == '__main__': main()