結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー Vincent Shaw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0