結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー navel_tos
提出日時 2024-02-05 23:47:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,609 bytes
コンパイル時間 374 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 77,852 KB
最終ジャッジ日時 2024-09-28 11:49:37
合計ジャッジ時間 12,239 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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:
        from collections import defaultdict
        def fact(N):
            A = defaultdict(int)
            for i in range(2, N):
                if i ** 2 > N: break
                while N % i == 0:
                    A[i] += 1
                    N //= i
            if N > 1: A[N] += 1
            return A
        D = defaultdict(int)
        for y in Y:
            A = fact(y)
            for i in A:
                D[i] = max(D[i], A[i])
        ans = 1
        for i in D:
            ans = ans * pow(i, D[i], MOD) % MOD
    print(ans)

solve_hard()
0