結果

問題 No.186 中華風 (Easy)
ユーザー kira924agekira924age
提出日時 2017-08-28 13:08:30
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,219 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 13,648 KB
最終ジャッジ日時 2024-11-06 08:26:16
合計ジャッジ時間 3,599 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
13,088 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

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 != a1 or ans % m2 != a2 or ans % m3 != a3:
    ans = -1

else:
    ans %= 10**9+7

print ans


"""
def modinv(a, n):
    return extgcd(a, n)[0] % n
def crt(eqn1, eqn2):
    x = x1 + (m1 // d) * (x2 - x1) * modinv(m1 // d, m2 // d)
    return x % m, m
n = int(input())
eqn = [ tuple(map(int, input().split())) for _ in range(n) ]
ans, _ = functools.reduce(crt, eqn)
if ans == 0:
    ans += functools.reduce(lcm, map(lambda it: it[1], eqn))
for x, y in eqn:
    if ans % y != x:
        ans = -1
        break
else:
    ans %= 10**9+7
print(ans)
"""
0