結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー kira924age
提出日時 2017-08-28 13:06:57
言語 Python2
(2.7.18)
結果
RE  
実行時間 -
コード長 765 bytes
コンパイル時間 420 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 13,632 KB
最終ジャッジ日時 2024-11-06 08:26:12
合計ジャッジ時間 3,962 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 4 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python2
# coding: utf-8

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)


def lcm(x, y):
    return x / gcd(x, y) * y


def extgcd(x, y):

    if y == 0:
        return [1, 0, x]

    a, b, g = extgcd(y, x%y)

    return [b, a - x/y * b, g]


def chinese(a1, a2, m1, m2):
    g = gcd(m1, m2)
    l = lcm(m1, m2)
    y = extgcd(m1, m2)[0]
    x = a1 + (a2-a1) * (m1/g) * y

    while x < 0:
        x += l

    return x

a1, m1 = map(int, raw_input().split())
a2, m2 = map(int, raw_input().split())
a3, m3 = map(int, raw_input().split())

ans = chinese(a1, a2, m1, m2)
ans = chinese(ans, a3, lcm(m1,m2), m3)

if ans % m1 != x1 or ans % m2 != x2 or ans % m3 != x3:
    ans = -1
 
else:
    ans %= 10**9+7

print ans
0