Fshl0

CRT

Feb 5th, 2021
91
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll crt() {
  2.     ll n, N = 1;
  3.     cin >> n;
  4.     for (ll i = 0; i < n; i++) {
  5.         cin >> p[i] >> r[i];
  6.         N *= p[i];
  7.         // L equiv r[i] (mod p[i])
  8.     }
  9.     bool fucked = false;
  10.     for (ll i = 0; i < n; i++)
  11.         for (ll j = i + 1; j < n; j++)
  12.             if (gcd (p[i], p[j]) != 1) fucked = true;
  13.     if (fucked) return -1;
  14.     ll L = 0;
  15.     for (ll i = 0; i < n; i++) {
  16.         ll y = N / p[i];
  17.         ll X, Y;
  18.         ll g = e_gcd (y, p[i], X, Y);
  19.         L += (r[i] * y * X) % N;
  20.         L %= N;
  21.     }
  22.     return (L + N) % N;
  23. }
RAW Paste Data