結果

問題 No.187 中華風 (Hard)
ユーザー pekempeypekempey
提出日時 2015-08-31 11:52:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 430 ms / 3,000 ms
コード長 2,889 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 179,836 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 16:47:56
合計ジャッジ時間 7,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 204 ms
5,376 KB
testcase_03 AC 203 ms
5,376 KB
testcase_04 AC 322 ms
5,376 KB
testcase_05 AC 310 ms
5,376 KB
testcase_06 AC 315 ms
5,376 KB
testcase_07 AC 324 ms
5,376 KB
testcase_08 AC 424 ms
5,376 KB
testcase_09 AC 430 ms
5,376 KB
testcase_10 AC 416 ms
5,376 KB
testcase_11 AC 318 ms
5,376 KB
testcase_12 AC 326 ms
5,376 KB
testcase_13 AC 265 ms
5,376 KB
testcase_14 AC 227 ms
5,376 KB
testcase_15 AC 197 ms
5,376 KB
testcase_16 AC 205 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 260 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 325 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) rep2 (i, 0, a)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) repr2 (i, 0, a)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

pair<ll, ll> extgcd(ll a, ll b) {
	if (b == 0) return make_pair(1, 0);
	auto p = extgcd(b, a % b);
	return make_pair(p.second, p.first - a / b * p.second);
}

ll modulo(ll a, ll m) {
	a %= m; a += m; a %= m;
	return a;
}

ll modinv(ll a, ll m) {
	if (a == 0) return -1;
	if (__gcd(a, m) != 1) return -1;
	return modulo(extgcd(a, m).first, m);
}

ll garner(vector<pair<ll, ll>> eq, ll m) {
	int n = eq.size();
	vector<ll> v;
	v.push_back(eq[0].first);
	rep2 (i, 1, n) {
		if (eq[i].second == 1) continue;
		ll coef = 1;
		ll sum = 0;
		rep (j, v.size()) {
			sum += coef * v[j];
			sum %= eq[i].second;
			coef *= eq[j].second;
			coef %= eq[i].second;
		}
		ll x = modulo(eq[i].first - sum, eq[i].second);
		ll inv = modinv(coef, eq[i].second);
		if (inv == -1) return -1;
		ll u = x * inv % eq[i].second;
		v.push_back(u);
	}
	ll res = 0;
	ll coef = 1;
	rep (i, v.size()) {
		res += coef * v[i];
		res %= m;
		coef *= eq[i].second;	
		coef %= m;
	}
	return res;
}

map<ll, ll> primefactor(ll n) {
	map<ll, ll> res;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			res[i]++;
			n /= i;
		}
	}
	if (n != 1) res[n]++;
	return res;
}

bool check(vector<pair<ll, ll>> eq) {
	rep (i, eq.size()) {
		rep2 (j, i + 1, eq.size()) {
			ll a1 = eq[i].first;
			ll a2 = eq[j].first;
			ll m1 = eq[i].second;
			ll m2 = eq[j].second;	
			ll g = __gcd(m1, m2);
			ll l = m1 / g * m2;
			if ((a2 - a1) % g != 0) return false;
		}
	}
	return true;
}

vector<pair<ll, ll>> normalize(vector<pair<ll, ll>> eq) {
	vector<map<ll, ll>> pf(eq.size());
	rep (i, eq.size()) {
		pf[i] = primefactor(eq[i].second);
	}
	map<ll, pair<ll, ll>> pnum; // prime, value, index
	rep (i, pf.size()) {
		for (auto p : pf[i]) {
			if (pnum[p.first].first < p.second) {
				pnum[p.first].first = p.second;
				pnum[p.first].second = i;
			}
		}	
	}
	for (auto p : pnum) {
		rep (i, eq.size()) if (i != p.second.second) {
			while (eq[i].second % p.first == 0) {
				eq[i].second /= p.first;
			}
			eq[i].first %= eq[i].second;
		}
	}
	return eq;
}

template<class T1, class T2>
ostream &operator <<(ostream &os, const pair<T1, T2> &p) {
	cout << "(" << p.first << ", " << p.second << ")";
	return os;
}

int main() {
	int n;
	cin >> n;
	vector<pair<ll, ll>> eq(n);
	rep (i, n) cin >> eq[i].first >> eq[i].second;
	if (!check(eq)) {
		cout << -1 << endl;
		return 0;
	}
	eq = normalize(eq);
	const ll mod = 1e9 + 7;
	bool zero = true;
	ll prod = 1;
	rep (i, eq.size()) {
		if (eq[i].first != 0) zero = false;
		prod *= eq[i].second;
		prod %= mod;
	}
	if (zero) {
		cout << prod << endl;
	} else {
		ll ans = garner(eq, mod);
		cout << ans << endl;
	}

	return 0;
}
0