結果

問題 No.187 中華風 (Hard)
ユーザー drken1215drken1215
提出日時 2015-04-19 23:43:27
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 8,686 bytes
コンパイル時間 2,818 ms
コンパイル使用メモリ 113,240 KB
実行使用メモリ 12,064 KB
最終ジャッジ日時 2023-09-18 01:49:07
合計ジャッジ時間 8,695 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
11,948 KB
testcase_01 AC 57 ms
7,584 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

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;
    
    while (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;
        }
    }
}
0