結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
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 mod) {
	a %= mod; a += mod; a %= mod;
	return a;
}
ll modpow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b /= 2;
	}
	return res;
}
ll modinv(ll a, ll mod) {
	return modulo(extgcd(a, mod).first, mod);
}

ll garner(vector<pair<ll, ll>> eq, ll mod) {
	eq.emplace_back(0, mod);
	int n = eq.size();
	vector<ll> coef(n, 1), sum(n, 0);
	rep (i, n - 1) {
		ll v = (eq[i].first - sum[i]) * modinv(coef[i], eq[i].second) % eq[i].second;
		if (v < 0) v += eq[i].second;
		rep (j, i + 1, n) {
			(sum[j] += coef[j] * v) %= eq[j].second;
			(coef[j] *= eq[i].second) %= eq[j].second;
		}
	}
	return sum.back();
}

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()) {
        rep (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