結果
| 問題 | No.187 中華風 (Hard) |
| ユーザー |
 drken1215
|
| 提出日時 | 2015-04-20 00:17:01 |
| 言語 | C++11 (gcc 11.4.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 49 ms
7,552 KB |
| testcase_01 | AC | 49 ms
7,680 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 | -- | - |
ソースコード
#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;
}
}