結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー pekempey
提出日時 2015-08-31 11:45:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,108 bytes
コンパイル時間 2,294 ms
コンパイル使用メモリ 180,220 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 16:47:00
合計ジャッジ時間 8,216 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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;
}

pair<ll, ll> solve_congruence(ll a1, ll m1, ll a2, ll m2) {
	ll g = __gcd(m1, m2);
	ll l = m1 / g * m2;
	auto p = extgcd(m1, m2);
	if ((a2 - a1) % g != 0) return make_pair(0, -1);
	p.first *= (a2 - a1) / g;
	ll x = p.first * m1 + a1;
	x %= l; x += l; x %= l;
	return make_pair(x, l);
}

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;
	ll ans = garner(eq, mod);
	if (ans == 0) {
		ll prod = 1;
		rep (i, eq.size()) {
			prod *= eq[i].second;
			prod %= mod;
		}	
		ans += prod;
	}
	cout << ans << endl;

	return 0;
}
0