結果

問題 No.187 中華風 (Hard)
ユーザー pazzle1230pazzle1230
提出日時 2019-08-11 20:28:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 207 ms / 3,000 ms
コード長 3,034 bytes
コンパイル時間 1,773 ms
コンパイル使用メモリ 174,000 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-14 00:33:00
合計ジャッジ時間 5,722 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
6,816 KB
testcase_01 AC 13 ms
6,944 KB
testcase_02 AC 173 ms
6,940 KB
testcase_03 AC 171 ms
6,940 KB
testcase_04 AC 205 ms
6,940 KB
testcase_05 AC 205 ms
6,940 KB
testcase_06 AC 205 ms
6,940 KB
testcase_07 AC 206 ms
6,940 KB
testcase_08 AC 139 ms
6,944 KB
testcase_09 AC 139 ms
6,940 KB
testcase_10 AC 139 ms
6,940 KB
testcase_11 AC 207 ms
6,940 KB
testcase_12 AC 206 ms
6,940 KB
testcase_13 AC 69 ms
6,940 KB
testcase_14 AC 69 ms
6,944 KB
testcase_15 AC 171 ms
6,940 KB
testcase_16 AC 173 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 10 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 157 ms
6,944 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 205 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

::std::int64_t gcd(::std::int64_t a, ::std::int64_t b) {
	while (b != 0) {
		::std::swap(a, b);
		b = b % a;
	}
	return a;
}

::std::int64_t lcm(::std::int64_t a, ::std::int64_t b) {
	return a / gcd(a, b) * b;
}

::std::pair<::std::int64_t, ::std::int64_t> extgcd(::std::int64_t a, ::std::int64_t b) {
	::std::pair<::std::int64_t, ::std::int64_t> pa(1, 0), pb(0, 1);
	while (b != 0) {
		::std::swap(a, b); ::std::swap(pa, pb);
		pb = ::std::make_pair(pb.first - pa.first * (b / a), pb.second - pa.second * (b / a));
		b = b % a;
	}
	return pa;
}


// return x (mod lcm(m_i)) and lcm(m_i) that satisfies x ≡ b_i (mod m_i) (中国剰余定理)
// if there isn't the answer, return (-1, -1)
// O(N log M)
::std::pair<::std::int64_t, ::std::int64_t> CRT(const ::std::vector<::std::int64_t> &b, ::std::vector<::std::int64_t> &m) {
	::std::int64_t ret = 0, M = 1;
	for (::std::size_t i = 0; i < b.size(); ++i) {
		::std::int64_t p, q;
		::std::int64_t d = gcd(M, m[i]);
		::std::tie(p, q) = extgcd(M, m[i]);
		if ((b[i] - ret) % d != 0) return ::std::make_pair(-1, -1);
		::std::int64_t tmp = (b[i] - ret) / d * p % (m[i] / d);
		ret += M * tmp;
		M *= m[i] / d;
	}
	return ::std::make_pair((ret + M) % M, M);
}



// Preprocessing for Garner algorithm
// make the elements of m coprime
// O(N^2)
std::int64_t pre_garner(std::vector<std::int64_t>& b, std::vector<std::int64_t>& m, const std::int64_t MOD) {
	std::int64_t res = 1;
	for (int i = 0; i < b.size(); i++) {
		for (int j = i + 1; j < b.size(); j++) {
			std::int64_t g = gcd(m[i], m[j]);

			if ((b[i] - b[j]) % g != 0) return -1;

			m[i] /= g; m[j] /= g;
			std::int64_t gi = gcd(m[i], g), gj = g / gi;
			do {
				g = gcd(gi, gj);
				gi *= g; gj /= g;
			} while (g != 1);

			m[i] *= gi; m[j] *= gj;
			b[i] %= m[i]; b[j] %= m[j];
		}
		res = (res * m[i]) % MOD;
	}
	return res;
}

// return x mod MOD
// It must be guranteed that all elements of m are coprime
// O(N^2)
std::int64_t garner(const std::vector<std::int64_t>& b, const std::vector<std::int64_t>& m, const std::int64_t MOD) {
	std::vector<std::int64_t> coeffs(b.size()+1, 1); 
	std::vector<std::int64_t> constants(b.size()+1, 0); 
	for (int i = 0; i < b.size(); ++i) {
		std::int64_t p, inv;
		std::tie(inv, p) = extgcd(coeffs[i], m[i]);
		std::int64_t t = (b[i] - constants[i]) * inv % m[i];
		if (t < 0) t += m[i];
		for (int j = i+1; j < b.size(); ++j) {
			constants[j] = (constants[j] + coeffs[j] * t) % m[j];
			coeffs[j] = (coeffs[j] * m[i]) % m[j];
		}
		constants.back() = (constants.back() + coeffs.back() * t) % MOD;
		coeffs.back() = (coeffs.back() * m[i]) % MOD;
	}
	return constants.back();
}

int main(void) {
	using namespace std;
	int64_t N;
	cin >> N;
	vector<int64_t> X(N), Y(N);
	bool all0 = 1;
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
		if (X[i] != 0) all0 = 0;
	}

	constexpr int64_t mod = 1e9+7;
	int64_t l = pre_garner(X, Y, mod);
	int64_t res = garner(X, Y, mod);
	if (l == -1 || all0) {
		cout << l << endl;
	} else {
		cout << res << endl;
	}
}
0