중국인의 나머지 정리 (Chinese Remainder Theorem)

# 중국인의 나머지 정리
import sys
input = sys.stdin.readline
​
def extgcd(a, b):
  if b == 0:
      return a, 1, 0
  d, x1, y1 = extgcd(b, a % b)
  return d, y1, x1 - (a // b) * y1
​
def mod_inv(a, m):
  d, x, y = extgcd(a, m)
  return x % m
​
def crt(a, m):
  M = 1
  for v in m:
      M *= v
  x = 0
  for ai, mi in zip(a, m):
      Mi = M // mi
      ti = mod_inv(Mi % mi, mi)
      x = (x + ai * Mi * ti) % M
  return x
​
k = int(input())
a = []
m = []
for _ in range(k):
  ai, mi = map(int, input().split())
  a.append(ai)
  m.append(mi)
print(crt(a, m))

// 중국인의 나머지 정리 (pairwise coprime)
import java.util.*;
import java.io.*;
public class Main {
  static long[] extgcd(long a, long b) {
      if (b == 0) return new long[]{a, 1, 0};
      long[] r = extgcd(b, a % b);
      return new long[]{r[0], r[2], r[1] - (a / b) * r[2]};
  }
  static long modInv(long a, long m) {
      long[] r = extgcd(a, m);
      long x = r[1] % m;
      return x < 0 ? x + m : x;
  }
  static long crt(long[] a, long[] m) {
      long M = 1, x = 0;
      for (long v : m) M *= v;
      for (int i = 0; i < a.length; i++) {
          long Mi = M / m[i];
          long ti = modInv(Mi % m[i], m[i]);
          x = (x + a[i] * Mi % M * ti) % M;
      }
      return x;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int k = Integer.parseInt(br.readLine());
      long[] a = new long[k], m = new long[k];
      for (int i = 0; i < k; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          a[i] = Long.parseLong(st.nextToken());
          m[i] = Long.parseLong(st.nextToken());
      }
      System.out.println(crt(a, m));
  }
}