結果

問題 No.186 中華風 (Easy)
ユーザー terasa
提出日時 2022-12-13 13:33:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 1,879 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 68,608 KB
最終ジャッジ日時 2024-11-07 09:06:31
合計ジャッジ時間 2,918 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Tuple, Callable, TypeVar, Optional
import sys
import itertools
import heapq
import bisect
import math
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key
import string

input = sys.stdin.readline

if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)


def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input()[:-1]


def extgcd(a: int, b: int) -> Tuple[int, int, int]:
    """solve ax + by = gcd(a, b)"""
    x, y, u, v = 1, 0, 0, 1
    while b:
        q, r = divmod(a, b)
        x -= q * u
        y -= q * v
        x, u = u, x
        y, v = v, y
        a, b = b, r
    return a, x, y


def crt(P: Tuple[int, int]) -> Tuple[int, int]:
    """return the smallest x that satisfies x ≡ a (mod m) for all (a, m) pairs and lcm(M)
    # reference: https://qiita.com/drken/items/ae02240cd1f8edfc86fd
    """
    """
    if there exist x s.t. x ≡ a1 (mod m1) and x ≡ a2 (mod m2),
    let g = gcd(m1, m2).
    since m1 and m2 are multiple of g, x ≡ a1 (mod g) and x ≡ a2 (mod g).
    therefore a1 ≡ a2 (mod g).

    there exist (p, q) s.t. m1 * p + m2 * q = gcd(m1, m2). (this can be obtained by extgcd)
    let g = gcd(m1, m2) and s = (a2 - a1) / g
    then m1 * p + m2 * q = g
    <=> m1 * p + m2 * q = (a2 - a1) / s
    <=> s * m1 * p + s * m2 * q = a2 - a1
    <=> a1 + s + m1 + p = a2 - s * m2 * q

    let x = a1 + s * m1 * p (= a2 - s * m2 * q)
    then x ≡ a1 (mod m1), x ≡ a2 (mod m2).
    """
    r = 0
    M = 1
    for a, m in P:
        g, p, q = extgcd(M, m)
        if (a - r) % g != 0:
            return (0, -1)
        s = (a - r) // g
        tmp = s * p % (m // g)
        r += M * tmp
        M *= m // g
    return (r, M)


P = [tuple(readints()) for _ in range(3)]
ans, lcm = crt(P)
print(ans if ans > 0 else lcm)
0