#20802 (C++11（廃止可能性あり）) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: drken1215
• 提出日時: 2015-04-20 00:17:01
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 9,355 bytes
• コンパイル時間: 2,005 ms
• コンパイル使用メモリ: 97,280 KB
• 実行使用メモリ: 14,624 KB
• 最終ジャッジ日時: 2024-07-04 15:48:07
• 合計ジャッジ時間: 7,448 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

ファイルパターン	結果
other	AC * 2 WA * 13 TLE * 1 -- * 9

ソースコード

#include <iostream>
#include <vector>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) 
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }


const long long MOD = 1000000007;

const int DEFAULT_SIZE = 125;
struct Bigint : vector<long long> {
    static const long long BASE = 100000000;
    static const int BASE_DIGIT = 8;
    int sign;
    
    Bigint() : vector<long long>(1, 0) { sign = 1; }
    Bigint(long long num) : vector<long long>(DEFAULT_SIZE, 0) {
        sign = 1; if (num < 0) sign = -1, num = -num;
        (*this)[0] = num; 
        (*this).normalize();
    }
    Bigint(int SIZE, long long num) : vector<long long>(SIZE, 0) {
        sign = 1; if (num < 0) sign = -1, num = -num;
        (*this)[0] = num;
        (*this).normalize();
    }
    
    Bigint& normalize() {
        long long c = 0;
        for (int i = 0;; ++i) {
            if (i >= (*this).size()) (*this).push_back(0);
            if ((*this)[i] < 0 && i+1 >= (*this).size()) (*this).push_back(0);
            while ((*this)[i] < 0) { (*this)[i+1] -= 1; (*this)[i] += BASE; }
            long long a = (*this)[i] + c;
            (*this)[i] = a % BASE;
            c = a / BASE;
            if (c == 0 && i == (*this).size()-1) break;
        }
        return (*this);
    }
    
    inline Bigint operator - () { 
        Bigint res = (*this); 
        bool allzero = true; for (int i = 0; i < res.size(); ++i) if (res[i] != 0) { allzero = false; break; }
        if (!allzero) res.sign *= -1; 
        return res; 
    }
    inline const Bigint& operator += (const Bigint &x);
    inline const Bigint& operator -= (const Bigint &x);
    inline const Bigint& operator *= (long long x);
    inline const Bigint& operator *= (const Bigint &x);
    inline const Bigint& operator /= (long long x);
    inline const Bigint& operator /= (const Bigint &x);
    inline const Bigint& operator %= (long long x);
    inline const Bigint& operator %= (const Bigint &x);
};

inline Bigint abs(const Bigint &x) {
    Bigint z = x;
    if (z.sign == -1) z.sign = 1;
    return z;
}
inline Bigint conv(string s) {
    Bigint res = 0;
    for (int i = 0; i < s.size(); ++i) {
        res += (long long)(s[i] - '0');
        if (i != s.size()-1) res *= 10;
    }
    return res;
}
ostream &operator << (ostream &os, Bigint x) {
    if (x.sign == -1) os << '-';
    int d = x.size()-1; 
    for (d = x.size()-1; d >= 0; --d) if (x[d] > 0) break;
    if (d == -1) os << 0;
    else os << x[d];
    for (int i = d-1; i >= 0; --i) { os.width(Bigint::BASE_DIGIT); os.fill('0'); os << x[i]; }
    return os;
}
istream &operator >> (istream &is, Bigint &x) {
    string s; is >> s;
    x = conv(s);
    return is;
}
bool operator > (Bigint x, Bigint y) {
    x.normalize(); y.normalize();
    if (x.sign > y.sign) return true;
    else if (x.sign < y.sign) return false;
    else {
        while (x.size() < y.size()) x.push_back(0);
        while (x.size() > y.size()) y.push_back(0);
        if (x.sign == 1) {
            for (int i = x.size()-1; i >= 0; --i) if (x[i] != y[i]) return x[i] > y[i];
            return false;
        }
        else {
            for (int i = x.size()-1; i >= 0; --i) if (x[i] != y[i]) return x[i] < y[i];
            return false;
        }
    }
}
bool operator < (Bigint x, Bigint y) { return y > x; }
bool operator <= (Bigint x, Bigint y) { return !(x > y); }
bool operator >= (Bigint x, Bigint y) { return !(y > x); }
bool operator != (Bigint x, Bigint y) { return (x > y) || (y > x); }
bool operator == (Bigint x, Bigint y) { return !(x > y) && !(y > x); }

inline Bigint operator + (Bigint x, Bigint y) {
    while (x.size() < y.size()) x.push_back(0);
    while (x.size() > y.size()) y.push_back(0);
    Bigint z((int)x.size(), 0);
    if (x.sign == y.sign) {
        z.sign = x.sign;
        for (int i = 0; i < x.size(); ++i) z[i] = x[i] + y[i];
    }
    else {
        if (x.sign == -1) swap(x, y);
        if (x >= -y) { z.sign = 1; for (int i = 0; i < x.size(); ++i) z[i] = x[i] - y[i]; }
        else { z.sign = -1; for (int i = 0; i < x.size(); ++i) z[i] = y[i] - x[i]; }
    }
    return z.normalize();
} 
inline Bigint operator - (Bigint x, Bigint y) {
    y = -y;
    return x + y;
}
inline Bigint operator * (Bigint x, long long a) {
    Bigint z((int)x.size(), 0);
    if ( (x.sign == 1 && a >= 0) || (x.sign == -1 && a < 0) ) z.sign = 1;
    else z.sign = -1;
    if (a < 0) a = -a;
    for (int i = 0; i < x.size(); ++i) z[i] = x[i] * a;
    return z.normalize();
}
inline Bigint operator * (Bigint x, Bigint y) {
    int tx = x.size()-1, ty = y.size()-1; 
    for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
    for (ty = y.size()-1; ty >= 0; --ty) if (y[ty] > 0) break;
    Bigint z(tx+ty+5, 0);
    if (x.sign == y.sign) z.sign = 1;
    else z.sign = -1;
    for (int i = 0; i <= tx; ++i) {
        for (int j = 0; j <= ty && i+j < z.size()-1; ++j) {
            long long val = x[i] * y[j] + z[i+j];
            z[i+j+1] += val / Bigint::BASE;
            z[i+j] = val % Bigint::BASE;
        }
    }
    return z.normalize();
}
pair<Bigint, long long> divmod(Bigint x, long long a) {
    long long c = 0, t = 0;
    for (int i = x.size()-1; i >= 0; --i) {
        t = Bigint::BASE * c + x[i];
        x[i] = t / a;
        c = t % a;
    }
    x.normalize();
    return pair<Bigint, long long>(x, c);
}
Bigint operator / (Bigint x, long long a) {
    return divmod(x, a).first;
}
long long operator % (Bigint x, long long a) {
    return divmod(x, a).second;
}
pair<Bigint, Bigint> divmod(Bigint x, Bigint y) {
    Bigint zero = 0;
    if (abs(x) < abs(y)) return pair<Bigint, Bigint>(zero, x);
    Bigint ay = abs(y), q((int)x.size(), 0), r((int)y.size(), 0);
    int tx = x.size()-1; 
    for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
    for (int i = tx; i >= 0; --i) {
        r = r * Bigint::BASE + x[i];
        long long lo = 0, hi = Bigint::BASE;
        if (r >= ay) {
            while (hi - lo > 1) {
                int mid = (hi + lo) / 2;
                if (ay * mid > r) hi = mid;
                else lo = mid;
            }
            r = r - ay * lo;
        }
        q[i] = lo;
    }
    if (x.sign == -1 || y.sign == -1) q.sign = -1, r.sign = -1;
    return make_pair(q.normalize(), r.normalize());
}
Bigint operator / (Bigint x, Bigint y) {
    return divmod(x, y).first;
}
Bigint operator % (Bigint x, Bigint y) {
    return divmod(x, y).second;
}
inline Bigint pow(Bigint a, long long n) {
    Bigint res = 1;
    while (n > 0) { if (n & 1) { res = res * a; } a = a * a; n >>= 1; }
    return res;
}
Bigint sqrt(Bigint num) {
    Bigint lo = 1, hi = num;
    while (hi - lo > 1) {
        Bigint med = (lo + hi) / 2;
        if (med * med > num) hi = med;
        else lo = med;
    }
    return lo;
}
inline const Bigint& Bigint::operator += (const Bigint &x) {*this = *this + x; return *this;}
inline const Bigint& Bigint::operator -= (const Bigint &x) {*this = *this - x; return *this;}
inline const Bigint& Bigint::operator *= (long long x) {*this = *this * x; return *this;}
inline const Bigint& Bigint::operator *= (const Bigint &x) {*this = *this * x; return *this;}
inline const Bigint& Bigint::operator /= (long long x) {*this = *this / x; return *this;}
inline const Bigint& Bigint::operator /= (const Bigint &x) {*this = *this / x; return *this;}
inline const Bigint& Bigint::operator %= (long long x) {*this = *this % x; return *this;}
inline const Bigint& Bigint::operator %= (const Bigint &x) {*this = *this % x; return *this;}



inline Bigint mod(Bigint a, Bigint m) {
    return (a % m + m) % m;
}

Bigint inv(Bigint a, Bigint m) {
    Bigint b = m, u = 1, v = 0;
    while (b != 0) {
        Bigint t = a/b;
        a -= t*b; swap(a, b);
        u -= t*v; swap(u, v);
    }
    return mod(u, m);
}

Bigint gcd(Bigint a, Bigint b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

pair<Bigint, Bigint> ChineseRem(vector<Bigint> vb, vector<Bigint> vm) {
    Bigint x = 0, m = 1, a, b, d;
    for (int i = 0; i < vb.size(); ++i) {
        a = m, b = vb[i] - x, d = gcd(vm[i], a);
        
        if (b % d != 0) return make_pair(0, -1);
        Bigint t = mod(b/d * inv(a/d, vm[i]/d), vm[i]/d);
        x += m * t;
        m *= vm[i]/d;
    }
    return make_pair(x % m, m);
}

int main() {
    int n;
    
    cin >> n;
    vector<Bigint> vb, vm;
    
    for (int i = 0; i < n; ++i) {
        Bigint b, m; cin >> b >> m;
        vb.push_back(b); vm.push_back(m);
    }
    
    pair<Bigint, Bigint> res = ChineseRem(vb, vm);
    
    if (res.second == -1) cout << -1 << endl;
    else {
        if (res.first == 0) cout << mod(res.second, MOD) << endl;
        else cout << mod(res.first, MOD) << endl;
    }
}