#中国剰余定理・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()