結果

問題 No.187 中華風 (Hard)
ユーザー kira924agekira924age
提出日時 2017-08-28 13:05:46
言語 Python2
(2.7.18)
結果
RE  
実行時間 -
コード長 765 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-06 08:26:08
合計ジャッジ時間 1,829 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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