#line 1 "test/math/garner/yuki187.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/187" #line 2 "src/Template.hpp" #define CUT #include using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, l, r) for (int i = (r); i --> (l);) #define all(c) begin(c), end(c) #ifdef LOCAL #define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__) template void debug_impl(string s, H&& h, Ts&&... ts) { cerr << '(' << s << "): (" << forward(h); ((cerr << ", " << forward(ts)), ..., (cerr << ")\n")); } #else #define debug(...) void(0) #endif template bool chmax(T& a, const T& b) { return b > a ? (a = b, true) : false; } template bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; } template istream& operator>>(istream& in, vector& v) { for (auto& e : v) in >> e; return in; } template void read(Args&... args) { (cin >> ... >> args); } template ostream& operator<<(ostream& out, const vector& v) { int n = v.size(); rep(i, 0, n) { out << v[i]; if (i + 1 != n) out << ' '; } return out; } template void print(H&& h, Ts &&... ts) { cout << h, ((cout << ' ' << forward(ts)), ..., (cout << '\n')); } struct io_setup_ { io_setup_() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(10); } } io_setup{}; #undef CUT #define NOTE compile command: \texttt{g++ -std=gnu++17 -Wall -Wextra -g -fsanitize=address -fsanitize=undefined \$\{file\} -o \$\{fileDirname\}/\$\{fileBasenameNoExtension\}} #undef NOTE #define NOTE \texttt{-DLOCAL} を加えると \texttt{debug(...)} による出力が有効となる #undef NOTE #line 3 "src/math/Garner.hpp" #define CUT #line 3 "src/math/ExtGCD.hpp" #define CUT constexpr long safe_mod(long long x, long long m) { return (x %= m) < 0 ? x + m : x; } // Returns `(x,g)` s.t. `g=\gcd(a,b)`, `xa\equiv g \pmod{b}`, and `0\leq x< \frac{b}{g}` constexpr pair inv_gcd(long long a, long long b) { assert(b > 0); a = safe_mod(a, b); if (a == 0) return { 0, b }; long long s = b, t = a, x = 0, y = 1; while (t) { long long u = s / t; s -= t * u, swap(s, t); x -= y * u, swap(x, y); } if (x < 0) x += b / s; return { x, s }; } // Returns `x` s.t. `xa\equiv 1 \pmod{m}`. // Requirement: `\gcd(a, m) = 1`. constexpr long long inv_mod(long long a, long long m) { auto [x, g] = inv_gcd(a, m); assert(g == 1); return x; } // Returns `(x_0,y_0,g)` s.t. `g=\gcd(a,b)`, `ax_0 + by_0 = g`, and `0\leq x_0<\frac{b}{g}`. // 一般解は `(x,y)=(x_0+k\cdot\dfrac{b}{g}, y_0-k\cdot\dfrac{a}{g})\;(k\in\mathbb{Z})` なので、`(x_0,y_0)` は `x` が非負の下で最小の解 constexpr tuple ext_gcd(long long a, long long b) { auto [x, g] = inv_gcd(a, b); return { x, (g - x * a) / b, g }; } #undef CUT #line 5 "src/math/Garner.hpp" // Returns `x \bmod m` s.t. `\forall (x_i,m_i) \in \mathtt{eq}.\;x=x_i \pmod{m_i}`. // Time Complexity: `\Theta(|\mathtt{eq}| ^ 2 \log \max m_i)` // Requairement: `m_i` are coprime int garner_coprime(vector> eq, int m) { const int n = eq.size(); vector a(n); auto f = [&](int i, long long mod) { long long res = 0, prd = 1; rep(j, 0, i) { (res += a[j] * prd) %= mod; (prd *= eq[j].second) %= mod; } return res; }; rep(i, 0, n) { auto [xi, mi] = eq[i]; a[i] = safe_mod(xi - f(i, mi), mi); rep(j, 0, i) (a[i] *= inv_mod(eq[j].second, mi)) %= mi; } return f(n, m); } // Returns `(x \bmod m, (\mathrm{lcm}_i\; m_i) \bmod m)` s.t. `\forall (x_i,m_i) \in \mathtt{eq}.\;x=x_i \pmod{m_i}`. // Time Complexity: `\Theta(|\mathtt{eq}| ^ 2 \log \max m_i)` pair garner(vector> eq, int m) { const int n = eq.size(); rep(i, 0, n) { auto &[xi, mi] = eq[i]; rep(j, 0, i) { auto &[xj, mj] = eq[j]; long long g = gcd(mi, mj); if ((xi - xj) % g) return { -1, -1 }; mi /= g, mj /= g; long long gi = gcd(mi, g); long long gj = g / gi; do g = gcd(gi, gj), gi *= g, gj /= g; while (g != 1); mi *= gi, mj *= gj, xi %= mi, xj %= mj; } } long long l = 1; for (auto &[_, mi] : eq) l = (l * mi) % m; return { garner_coprime(eq, m), l }; } #undef CUT #line 4 "test/math/garner/yuki187.test.cpp" int main() { int n; read(n); bool all_zero = false; vector> eq(n); for (auto &[x, m] : eq) { read(x, m); all_zero &= x == 0; } const int m = 1000000007; auto [ans, lcm] = garner(eq, m); if (ans == -1) { print(-1); } else { print(all_zero ? lcm : ans); } }