Fshl0

MyCRT

Mar 16th, 2021
677
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool Crt (vector <ll>& Rems, vector <ll>& Mods, ll& x) {
  2.     ll r1 = x = Rems[0], m1 = Mods[0], n = Rems.size();
  3.     for (int i = 1; i < n; i++) {
  4.         ll r2 = Rems[i], m2 = Mods[i];
  5.         ll c = r2 - r1, g = gcd (m1, m2), p, q, l = lcm (m1, m2);
  6.         if (Flex (r1, g) != Flex (r2, g))
  7.             return false;
  8.         g = DoExtendedGCD (m1, -m2, p, q);
  9.         ll X = mul (Flex (p, l), Flex (c / g, l), l);
  10.         X = Flex (X, l);
  11.         x = r1 + mul (X, m1, l);
  12.         x = Flex (x, l);
  13.         r1 = x, m1 = l;
  14.     }
  15.     return true;
  16. }
RAW Paste Data