結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー satama123
提出日時 2026-03-28 12:39:08
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,768 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 356 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 52,864 KB
最終ジャッジ日時 2026-03-28 12:39:17
合計ジャッジ時間 2,838 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 数学的なもの

def euclid_algorithm(a, b):
    """ユークリッド互除法
    自然数a, bの最大公約数を求める
    """
    while b != 0:
        a %= b
        a, b = b, a    
    return a

def extended_euclid_algorithm(x, y):
    """拡張ユークリッド互除法
    自然数a, bに対して、以下を満たす整数x,yを求める
    ax + by = gcd(a, b)
    b=0でも動くはず
    """
    K = []
    while y != 0:
        k = x // y
        x, y = y, x%y
        K.append(k)
    
    a, b, c, d = 1, 0, 0, 1
    for i in reversed(range(len(K))):
        a, b, c, d = b, a-K[i]*b, d, c-K[i]*d
    return a, b

class ModuloCalculation:
    def __init__(self, mod):
        self.mod = mod

    def inverse_prime_mod(self, a):
        """ある素数modを法としたときのaの逆元を求める"""
        return pow(a, self.mod-2, self.mod)

    def inverse_composite_mod(self, a):
        """ある合成数modを法としたときのaの逆元を求める
        modとaが互いに素である必要がある。
        """
        ef = self.euler_function(self.mod)
        return pow(a, ef-1, self.mod)
    
    def euler_function(self, x):
        """xのオイラー関数の値を求める
        x = p1^{e1}p2^{e2}...pn^{en} -> x * (p1-1)/p1 * (p2-1)/p2 ... (pn-1)/pn
        であらわされ、x以下のxと互いに素な自然数の個数と等しい。
        """
        i = 2
        ans = x
        while i*i < x:
            if x % i == 0:
                ans = ans // i * (i - 1)
                j = x // i
                ans = ans // j * (j - 1)
            i += 1
        if i * i == x:
            ans = ans // i * (i - 1)
        if ans == x : ans -= 1
        return ans
               
    def __chinese_remainder_theory(self, b1, m1, b2, m2):
        """
        x ≡ bi (mod pi) 1 <= i <= N
        を満たす整数xが0 <= x < Πpiの範囲にただ一つ存在する。
        """
        d = euclid_algorithm(m1, m2)
        p, q  = extended_euclid_algorithm(m1, m2)
        if (b2 - b1) % d != 0:
            return -1, -1 # 解なし
        m = m1 * m2 // d
        tmp = (b2 - b1) // d * p % (m2 // d)
        r = (b1 + m1 * tmp) % m
        return r, m

    def chinese_remainder_theory(self, B:list, M:list):
        b = B[0]
        m = M[0]
        for i in range(1, len(B)):
            b, m = self.__chinese_remainder_theory(b, m, B[i], M[i])
            if m == -1:
                return -1, -1
        return b, m


if __name__ == "__main__":
    mc = ModuloCalculation(10)
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    e, f = map(int, input().split())
    B = [a, c, e]
    M = [b, d, f]
    r, m = mc.chinese_remainder_theory(B, M)
    print(r)
0