记录编号	603179	评测结果	AAAAAAAAAA
题目名称	3479.[POJ 2891]表达整数的奇怪方式	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2025-07-09 17:52:34	内存使用	1.52 MiB

#include <cstdio>
typedef __int128 int128;

void ParseIn();
void Core();
void WriteOut();

int main() {
  freopen("strangeway.in", "r", stdin);
  freopen("strangeway.out", "w", stdout);
  ParseIn();
  Core();
  WriteOut();
  return 0;
}

template <typename T> T read();
template <typename T> void write(T, char);
template <typename T> T gcd(T, T);
template <typename T> T lcm(T, T);
template <typename T> T exgcd(T, T, T &, T &);

int n;
int128 r[30], m[30];

void ParseIn() {
  n = read<int>();
  for (int i = 1; i <= n; ++i) {
    m[i] = read<int128>(), r[i] = read<int128>();
  }
}

int128 ans;
void Core() {
  ans = r[1];
  int128 M = m[1];
  for (int i = 2; i <= n; ++i) {
    int128 t, y, d = exgcd(M, m[i], t, y), c = ((r[i] - ans) % m[i] + m[i]) % m[i];
    if (c % d) {
      ans = -1;
      break;
    }
    t = t * c / d;
    ans = ans + t * M;
    M = lcm(M, m[i]);
    ans = (ans % M + M) % M;
  }
}

void WriteOut() {
  write(ans, '\n');
}

template <typename T> T gcd(T x, T y) {
  return y == 0 ? x : gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  return x / gcd(x, y) * y;
}

template <typename T> T exgcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  T d = exgcd(b, a % b, x, y);
  T z = x;
  x = y;
  y = z - y * (a / b);
  return d;
}

#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}
#undef isdigit

template <typename T> void write(T x, char ed) {
  if (x < 0) x = -x, putchar('-');
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}