#include #include //#include using namespace std; #define rep(i, a) for (int i = (int)0; i < (int)a; ++i) #define repl(i, a) for (long long i = (long long)0; i < (long long)a; ++i) #define rrep(i, a) for (int i = (int)a; i > -1; --i) #define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i) #define REPL(i, a, b) for (long long i = (long long)a; i < (long long)b; ++i) #define RREP(i, a, b) for (int i = (int)a; i > b; --i) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define fi first #define se second using ll = long long; constexpr ll mod = 1e9 + 7; constexpr ll mod_998244353 = 998244353; constexpr ll INF = 1LL << 60; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //using lll = boost::multiprecision::cpp_int; template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } ll mypow(ll x, ll n, const ll &p = -1) { // x^nをmodで割った余り if (p != -1) { x = (x % p + p) % p; } ll ret = 1; while (n > 0) { if (n & 1) { if (p != -1) ret = (ret * x) % p; else ret *= x; } if (p != -1) x = (x * x) % p; else x *= x; n >>= 1; } return ret; } template struct myrand { random_device seed; mt19937 mt; myrand() : mt(seed()) {} T operator()(T a, T b) { //[a,b) uniform_int_distribution dist(a, b - 1); return dist(mt); } }; //using namespace atcoder; //------------------------ //------------------------ //------------------------ //------------------------ //------------------------ template T extgcd(T a,T b,T &x,T &y){ T d=a; if(b==0){ x=1,y=0; }else{ d=extgcd(b,a%b,y,x); y-=a/b*x; } return d; } template T modinv(T a,T m){ T x,y; if(extgcd(a,m,x,y)==1){ return (x%m+m)%m; } return -1;//no inv } template T preGarner(vector &r,vector &m,T MOD=-1){ assert(r.size()==m.size()); T LCM=1; int n=r.size(); for(int i=0;i(m[i],m[j]); if((r[i]-r[j])%g!=0)return -1; m[i]/=g; m[j]/=g; T gi=gcd(m[i],g),gj=g/gi; while(g!=1){ g=gcd(gi,gj); gi*=g,gj/=g; } m[i]*=gi,m[j]*=gj; r[i]%=m[i],r[j]%=m[j]; } } for(int i=0;i pair CRT_Garner(vector &r,vector &m,T MOD=-1){ assert(r.size()==m.size()); T LCM=preGarner(r,m,MOD); if(LCM==-1){ return make_pair(0,0); } T prod_m=1,prod_t=0; int n=r.size(); for(int i=0;i>n; vectorr(n),m(n); rep(i,n){ cin>>r[i]>>m[i]; } auto [R,M]=CRT_Garner(r,m,mod); cout<<(M==0?-1:(R==0?M:R))<<"\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); solve(); return 0; }