关于龟速乘的一个问题

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void read() {}
template<typename T, typename ...U> void read(T &x, U& ...arg) {
  x = 0; int f = 1; char ch = getchar();
  while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f; read(arg...);
}

void write() {}
template<typename T> void write(T x) {
  if (x < 0) { putchar('-'), x = -x; }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

template<typename T, typename U> void write(T x, U y) {
  write(x); putchar(y);
}

template<typename T> void chkmin(T &a, T b) { a = min(a, b); }
template<typename T> void chkmax(T &a, T b) { a = max(a, b); }

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)

int n;
i64 a1, m1, a2, m2, p;

i64 mul(i64 a, i64 b, i64 mod) {
  i64 res = 0;

  for (; b; b >>= 1) {
    if (b & 1) res = (res + a) % mod;
    a = (a + a) % mod;
  }

  return res;
}

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
  if (!b) return x = 1, y = 0, a;
  i64 d = exgcd(b, a % b, y, x); y -= a / b * x;
  return d;
}

void exCRT() {
  read(m1, a1);

  rep(i, 1, n - 1) {
    read(m2, a2);
    i64 d = exgcd(m1, m2, p, *new i64);
    i64 dif = ((a2 - a1) % m2 + m2) % m2;  
    if (dif % d) { return puts("-1"), void(); }
    p = mul(p, dif / d, m2); (a1 += mul(p, m1, m1 / d * m2)) %= (m1 / d * m2);
    m1 = m1 / d * m2; a1 = (a1 % m1 + m1) % m1;
  }

  write(a1);
}

int main() {
#ifdef LOCAL
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  auto start_time = chrono::high_resolution_clock::now();
#endif

  read(n); exCRT();

#ifdef LOCAL
  auto end_time = chrono::high_resolution_clock::now();
  auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
  cerr << "Time cost " << duration.count() << " ms" << endl; 
#endif
  return 0;
}

// START AT 2025 / 07 / 22 08 : 58 : 28

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

void read() {}
template<typename T, typename ...U> void read(T &x, U& ...arg) {
  x = 0; int f = 1; char ch = getchar();
  while (ch > '9' || ch < '0') { if (ch == '-') f = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f; read(arg...);
}

void write() {}
template<typename T> void write(T x) {
  if (x < 0) { putchar('-'), x = -x; }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

template<typename T, typename U> void write(T x, U y) {
  write(x); putchar(y);
}

template<typename T> void chkmin(T &a, T b) { a = min(a, b); }
template<typename T> void chkmax(T &a, T b) { a = max(a, b); }

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)

int n;
i64 a1, m1, a2, m2, p;

i64 mul(i64 a, i64 b, i64 mod) {
  i64 res = 0;

  for (; b; b >>= 1) {
    if (b & 1) res = (res + a) % mod;
    a = (a + a) % mod;
  }

  return res;
}

i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
  if (!b) return x = 1, y = 0, a;
  i64 d = exgcd(b, a % b, y, x); y -= a / b * x;
  return d;
}

void exCRT() {
  read(m1, a1);

  rep(i, 1, n - 1) {
    read(m2, a2);
    i64 d = exgcd(m1, m2, p, *new i64);
    i64 dif = ((a2 - a1) % m2 + m2) % m2;  
    if (dif % d) { return puts("-1"), void(); }
    p = mul(p, dif / d, m2); a1 += mul(m1, p, m1 / d * m2);
    m1 = m1 / d * m2; a1 = (a1 % m1 + m1) % m1;
  }

  write(a1);
}

int main() {
#ifdef LOCAL
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);
  auto start_time = chrono::high_resolution_clock::now();
#endif

  read(n); exCRT();

#ifdef LOCAL
  auto end_time = chrono::high_resolution_clock::now();
  auto duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time);
  cerr << "Time cost " << duration.count() << " ms" << endl; 
#endif
  return 0;
}

// START AT 2025 / 07 / 22 08 : 58 : 28