結果

問題 No.187 中華風 (Hard)
ユーザー navel_tosnavel_tos
提出日時 2024-02-05 23:34:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,152 bytes
コンパイル時間 486 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 77,312 KB
最終ジャッジ日時 2024-09-28 11:49:04
合計ジャッジ時間 11,699 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
62,464 KB
testcase_01 AC 50 ms
61,952 KB
testcase_02 AC 654 ms
76,672 KB
testcase_03 AC 641 ms
76,516 KB
testcase_04 AC 655 ms
76,536 KB
testcase_05 AC 666 ms
76,160 KB
testcase_06 AC 726 ms
76,416 KB
testcase_07 AC 736 ms
76,288 KB
testcase_08 AC 540 ms
77,312 KB
testcase_09 AC 502 ms
76,800 KB
testcase_10 AC 515 ms
77,292 KB
testcase_11 AC 746 ms
76,672 KB
testcase_12 AC 685 ms
76,416 KB
testcase_13 AC 175 ms
76,544 KB
testcase_14 AC 190 ms
76,928 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 36 ms
52,992 KB
testcase_18 AC 46 ms
61,056 KB
testcase_19 AC 34 ms
52,224 KB
testcase_20 AC 518 ms
76,288 KB
testcase_21 AC 36 ms
52,224 KB
testcase_22 AC 673 ms
76,908 KB
testcase_23 WA -
testcase_24 AC 35 ms
52,736 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)

def solve_hard():
    N = int(input())
    X,Y = [],[]
    for _ in range(N):
        x,y = map(int,input().split())
        X.append(x)
        Y.append(y)
    MOD = 10 ** 9 + 7
    CRT = CRT_Garner()
    ans = CRT.Garner(X,Y,MOD)
    if ans == 0:
        ans = Y[0] * Y[1] * Y[2] // CRT.gcd(CRT.gcd(Y[0], Y[1]), Y[2]) % MOD
    print(ans)

solve_hard()
0