結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:54:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 1,224 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 54,376 KB
最終ジャッジ日時 2025-03-20 18:55:54
合計ジャッジ時間 1,855 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)

def modinv(a, m):
    d, x, y = extended_gcd(a, m)
    if d != 1:
        return None
    else:
        return x % m

def crt(a1, m1, a2, m2):
    d = math.gcd(m1, m2)
    c = a2 - a1
    if c % d != 0:
        return None
    m1_prime = m1 // d
    m2_prime = m2 // d
    c_prime = c // d
    inv = modinv(m1_prime, m2_prime)
    if inv is None:
        return None
    k0 = (c_prime * inv) % m2_prime
    a_result = a1 + k0 * m1
    lcm = m1 // d * m2
    a_result %= lcm
    return (a_result, lcm)

def main():
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    x3, y3 = map(int, input().split())
    
    # Merge first two equations
    res1 = crt(x1, y1, x2, y2)
    if res1 is None:
        print(-1)
        return
    a, m = res1
    
    # Merge with third equation
    res2 = crt(a, m, x3, y3)
    if res2 is None:
        print(-1)
        return
    a_final, m_final = res2
    
    # Calculate the smallest positive solution
    print(a_final if a_final != 0 else m_final)

if __name__ == '__main__':
    main()
0