結果

問題 No.187 中華風 (Hard)
ユーザー navel_tosnavel_tos
提出日時 2024-02-05 23:55:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,656 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 77,228 KB
最終ジャッジ日時 2024-02-05 23:56:13
合計ジャッジ時間 12,495 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 656 ms
76,076 KB
testcase_03 AC 690 ms
76,212 KB
testcase_04 AC 703 ms
76,076 KB
testcase_05 AC 714 ms
76,084 KB
testcase_06 AC 761 ms
75,948 KB
testcase_07 AC 781 ms
76,340 KB
testcase_08 AC 551 ms
76,848 KB
testcase_09 AC 584 ms
76,848 KB
testcase_10 AC 553 ms
76,848 KB
testcase_11 AC 784 ms
75,948 KB
testcase_12 AC 718 ms
75,944 KB
testcase_13 AC 167 ms
76,000 KB
testcase_14 AC 178 ms
76,004 KB
testcase_15 AC 695 ms
76,848 KB
testcase_16 AC 733 ms
77,228 KB
testcase_17 AC 36 ms
53,460 KB
testcase_18 WA -
testcase_19 AC 36 ms
53,460 KB
testcase_20 AC 577 ms
75,944 KB
testcase_21 AC 36 ms
53,460 KB
testcase_22 AC 724 ms
76,332 KB
testcase_23 AC 36 ms
53,460 KB
testcase_24 AC 36 ms
53,460 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 and all(x == 0 for x in X):
        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