結果

問題 No.186 中華風 (Easy)
ユーザー navel_tosnavel_tos
提出日時 2024-02-05 23:32:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 2,810 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 54,228 KB
最終ジャッジ日時 2024-09-28 11:48:49
合計ジャッジ時間 1,959 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
53,220 KB
testcase_01 AC 37 ms
53,728 KB
testcase_02 AC 37 ms
52,804 KB
testcase_03 AC 36 ms
53,064 KB
testcase_04 AC 37 ms
53,584 KB
testcase_05 AC 37 ms
53,976 KB
testcase_06 AC 38 ms
53,324 KB
testcase_07 AC 37 ms
52,900 KB
testcase_08 AC 37 ms
53,936 KB
testcase_09 AC 37 ms
54,228 KB
testcase_10 AC 36 ms
52,764 KB
testcase_11 AC 37 ms
53,852 KB
testcase_12 AC 38 ms
53,420 KB
testcase_13 AC 37 ms
52,532 KB
testcase_14 AC 37 ms
53,188 KB
testcase_15 AC 37 ms
53,016 KB
testcase_16 AC 37 ms
52,952 KB
testcase_17 AC 36 ms
54,108 KB
testcase_18 AC 37 ms
53,344 KB
testcase_19 AC 36 ms
53,152 KB
testcase_20 AC 36 ms
53,688 KB
testcase_21 AC 37 ms
53,620 KB
testcase_22 AC 36 ms
53,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#中国剰余定理・Garner algorithm

#中国剰余定理・Garner algorithm
class CRT_Garner:
    gcd = lambda self, x, y: self.gcd(y, x % y) if y else abs(x)
    def _reassign(self, Y1, Y2):  #N ≡ X1 mod Y1 ≡ X2 mod Y2  gcd(Y1, Y2) = 1に振り直し
        G = self.gcd(Y1, Y2)
        a, b = Y1 // G, Y2 // G
        c = self.gcd(a, G)  #gcd(A,B)のうち、Aの固有の素因数をcに集める
        d = G // c
        g = self.gcd(c, d)
        while g > 1:
            c, d = c * g, d // g
            g = self.gcd(c, d)
        return a * c, b * d
    def euclid(self, A, B):  #Ax + By = gcd(A,B) を満たす(x,y)の組を返す
        G = self.gcd(A, B)
        a,b = A // G, B // G
        x = pow(a, -1, b)
        y = (1 - a * x) // b
        return x, y
    def CRT(self, X1, Y1, X2, Y2):  #N ≡ X1 mod Y1 ≡ X2 mod Y2  解なしなら-1
        if (X2 - X1) % self.gcd(Y1, Y2) != 0: return -1
        return ( (X2 - X1) * pow(Y1, -1, Y2) % Y2 ) * Y1 + X1

    #MODは素数とする。GarnerのアルゴリズムでN mod MODを計算する
    def Garner(self, X_list, Y_list, MOD = None):  #X_list: [X1, X2, ･･･]
        if len(X_list) != len(Y_list): return -1
        for i in range(len(Y_list)):  #解なしの判定
            for j in range(i + 1, len(Y_list)):
                if i >= j: continue
                Y1, Y2 = Y_list[i], Y_list[j]
                if (X_list[i] - X_list[j]) % self.gcd(Y1, Y2) != 0: return -1
                Y_list[i], Y_list[j] = self._reassign(Y1, Y2)
                X_list[i], X_list[j] = X_list[i] % Y_list[i], X_list[j] % Y_list[j]
        if MOD == None:
            ans, rem = 0, 1
            for X,Y in zip(X_list, Y_list): ans, rem = self.CRT(ans, rem, X, Y), rem * Y
            return ans
        for X,Y in zip(X_list, Y_list):
            if Y % MOD == 0: return X % MOD
        Y_list.append(MOD)
        Xg = [X_list[0] % y for y in Y_list]  #Xg[i]: 現在までのX mod Yi
        Yg = [1] * len(Y_list)  #Yg[i]: prod(Y0 ～ Yi-1) mod Yi
        for i in range(1, len(Y_list) - 1):
            for j in range(i, len(Y_list)):  #Yg[j]の計算
                Yg[j] = Yg[j] * Y_list[i-1] % Y_list[j]
            Xi, Yi = X_list[i], Y_list[i]
            vi = (Xi - Xg[i]) * pow(Yg[i], -1, Yi) % Yi  #vi * Yg[i] ≡ Xi - Xg[i] mod Yi
            for j in range(i, len(Y_list)):
                Xg[j] = (Xg[j] + vi * Yg[j]) % Y_list[j]
        Y_list.pop()
        return Xg[-1]
 

'''
ここからverify用コード
'''
def solve_easy():
    X,Y = [],[]
    for _ in range(3):
        x,y = map(int,input().split())
        X.append(x)
        Y.append(y)
    CRT = CRT_Garner()
    ans = CRT.Garner(X,Y)
    if ans == 0:
        ans += Y[0] * Y[1] * Y[2] // CRT.gcd(CRT.gcd(Y[0], Y[1]), Y[2])
    print(ans)

solve_easy()
0