中国剩余定理

解决以下方程组

{

$x\ \equiv a_1(mod\ n_1)$

$x\ \equiv a_2(mod\ n_2)$

$x\ \equiv a_3(mod\ n_3)$

}

//k 个数，a a数组，r m
LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}