結果

問題 No.186 中華風 (Easy)
ユーザー tcltktcltk
提出日時 2021-03-01 18:23:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 2,356 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 86,924 KB
最終ジャッジ日時 2024-04-14 03:46:40
合計ジャッジ時間 4,200 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
86,892 KB
testcase_01 AC 123 ms
86,896 KB
testcase_02 AC 126 ms
86,924 KB
testcase_03 AC 123 ms
86,632 KB
testcase_04 AC 123 ms
86,384 KB
testcase_05 AC 124 ms
86,404 KB
testcase_06 AC 122 ms
86,584 KB
testcase_07 AC 121 ms
86,404 KB
testcase_08 AC 123 ms
86,648 KB
testcase_09 AC 124 ms
86,800 KB
testcase_10 AC 124 ms
86,636 KB
testcase_11 AC 123 ms
86,800 KB
testcase_12 AC 123 ms
86,532 KB
testcase_13 AC 121 ms
86,420 KB
testcase_14 AC 122 ms
86,340 KB
testcase_15 AC 122 ms
86,776 KB
testcase_16 AC 125 ms
86,612 KB
testcase_17 AC 123 ms
86,660 KB
testcase_18 AC 122 ms
86,716 KB
testcase_19 AC 125 ms
86,880 KB
testcase_20 AC 123 ms
86,600 KB
testcase_21 AC 125 ms
86,908 KB
testcase_22 AC 125 ms
86,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#region Header
#!/usr/bin/env python3
# from typing import *

import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq


def input():
    return sys.stdin.readline()[:-1]


# sys.setrecursionlimit(1000000)
#endregion

# _INPUT = """0 750992
# 0 596522
# 0 718614
# """
# sys.stdin = io.StringIO(_INPUT)

def inv_gcd(a, b):
    a %= b
    if a == 0: return b, 0
    # 初期状態
    s, t = b, a
    m0, m1 = 0, 1
    while t:
        # 遷移の準備
        u = s // t

        # 遷移
        s -= t * u
        m0 -= m1 * u

        # swap
        s, t = t, s
        m0, m1 = m1, m0

    if m0 < 0: m0 += b // s
    return s, m0


# def crt(r: typing.List[int], m: typing.List[int]) -> typing.Tuple[int, int]:
def crt(r, m):
    assert len(r) == len(m)

    n = len(r)

    # Contracts: 0 <= r0 < m0
    r0 = 0
    m0 = 1
    for i in range(n):
        assert 1 <= m[i]
        r1 = r[i] % m[i]
        m1 = m[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue

        # assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)

        '''
        (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
        r2 % m0 = r0
        r2 % m1 = r1
        -> (r0 + x*m0) % m1 = r1
        -> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)
        -> x = (r1 - r0) / g * inv(u0) (mod u1)
        '''

        # im = inv(u0) (mod u1) (0 <= im < u1)
        g, im = inv_gcd(m0, m1)

        u1 = m1 // g
        # |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
        if (r1 - r0) % g:
            return (0, 0)

        # u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
        x = (r1 - r0) // g % u1 * im % u1

        '''
        |r0| + |m0 * x|
        < m0 + m0 * (u1 - 1)
        = m0 + m0 * m1 / g - m0
        = lcm(m0, m1)
        '''

        r0 += x * m0
        m0 *= u1  # -> lcm(m0, m1)
        if r0 < 0:
            r0 += m0

    return (r0, m0)

def main():
    X1, Y1 = map(int, input().split())
    X2, Y2 = map(int, input().split())
    X3, Y3 = map(int, input().split())
    r, m = crt([X1, X2, X3], [Y1, Y2, Y3])
    if r == 0 and m == 0:
        print(-1)
    elif r == 0:
        print(m)
    else:
        print(r)

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