結果

問題 No.187 中華風 (Hard)
ユーザー 東前頭十一枚目東前頭十一枚目
提出日時 2019-09-26 17:07:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 362 ms / 3,000 ms
コード長 3,492 bytes
コンパイル時間 1,648 ms
コンパイル使用メモリ 171,904 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 08:02:36
合計ジャッジ時間 6,812 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 242 ms
6,940 KB
testcase_03 AC 236 ms
6,940 KB
testcase_04 AC 361 ms
6,940 KB
testcase_05 AC 360 ms
6,944 KB
testcase_06 AC 362 ms
6,944 KB
testcase_07 AC 360 ms
6,940 KB
testcase_08 AC 223 ms
6,940 KB
testcase_09 AC 222 ms
6,940 KB
testcase_10 AC 218 ms
6,944 KB
testcase_11 AC 361 ms
6,940 KB
testcase_12 AC 361 ms
6,944 KB
testcase_13 AC 42 ms
6,944 KB
testcase_14 AC 42 ms
6,940 KB
testcase_15 AC 134 ms
6,940 KB
testcase_16 AC 137 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 3 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 275 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 360 ms
6,944 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct ChineseRemainderTheorem {
	inline T modulo(T x, const T MOD) {
		if(0 <= x and x < MOD) return x;
		x %= MOD;
		if(x < 0) x += MOD;
		return x;
	}
	// gcd(a, b)
	T exGCD(T a, T b) {
		T _p, _q;
		return exGCD(a, b, _p, _q);
	}
	// gcd(a, b)
	// ap + bq = gcd(a, b)を満たす(p, q)
	T exGCD(T a, T b, T &p, T &q) {
		if(b == 0) {
			// gcd(a, b)p + 0q = gcd(a, b)
			p = 1, q = 0;
			return a;
		}
		T ret = exGCD(b, a % b, q, p);
		q -= a / b * p;
		return ret;
	}
	// Garnerの前処理（互いに素にする）
	// lcm(mod) % MOD
	T normalisation(vector<T> &b, vector<T> &mod, const T MOD) {
		for(int i = 0; i < (int)b.size(); ++i) {
			for(int j = 0; j < i; ++j) {
				T g = exGCD(mod[i], mod[j]);
				// 必要十分性の確認
				if ((b[i] - b[j]) % g != 0) throw "NOT FOUND";
				mod[i] /= g;
				mod[j] /= g;
				T gi = exGCD(mod[i], g);
				T gj = g / gi;
				// 共通する場合，iの方が指数大
				while(true) {
					T gg = exGCD(gi, gj);
					if(gg == 1) break;
					gi *= gg, gj /= gg;
				}
				mod[i] *= gi;
				mod[j] *= gj;
				b[i] = modulo(b[i], mod[i]);
				b[j] = modulo(b[j], mod[j]);
			}
		}
		T ret = 1;
		for(int i = 0; i < (int)b.size(); ++i) {
			ret *= mod[i];
			ret = modulo(ret, MOD);
		}
		return ret;
	}
	// x ≡ b(mod m)を満たすx(mod M (= lcm m))
	T get(vector<T> &b, vector<T> &mod) {
		// x ≡ 0(mod 1)は全ての整数
		T x = 0, MOD = 1;
		for(int i = 0; i < (int)b.size(); ++i) {
			T p, _q;
			T d = exGCD(MOD, mod[i], p, _q);
			// 必要十分性の確認
			if((x - b[i]) % d != 0) throw "NOT FOUND";
			// nextMOD = MOD * (mod[i] / d)なので部分的にmodが取れてオーバーフロー回避
			x = x - modulo((x - b[i]) / d * p, (mod[i] / d)) * MOD;
			// lcm(M, m) = M * m / gcd(M, m)
			MOD = MOD * (mod[i] / d);
			x = modulo(x, MOD);
		}
		return modulo(x, MOD);
	}
	T Garner(vector<T> &b, vector<T> &mod, T MOD = numeric_limits<T>::max()) {
		try {
			normalisation(b, mod, MOD);
		}
		catch(...) {
			throw "NOT FOUND";
		}
		vector<T> p(b.size());
		for(int i = 0; i < (int)b.size(); ++i) {
			p[i] = b[i] % mod[i];
			for(int j = 0; j < i; ++j) {
				T inv, _tmp;
				exGCD(mod[j], mod[i], inv, _tmp);
				inv = modulo(inv, mod[i]);
				p[i] = (p[i] - p[j]) * inv;
				p[i] = modulo(p[i], mod[i]);
			}
		}
		// 復元
		T ret = 0;
		for(int i = 0; i < (int)b.size(); ++i) {
			T tmp = modulo(p[i], MOD);
			for(int j = 0; j < i; ++j) {
				tmp *= mod[j];
				tmp = modulo(tmp, MOD);
			}
			ret += tmp;
			ret = modulo(ret, MOD);
		}
		return ret;
	}
};

int main() {
	const int MOD = 1e9 + 7;
	int n; cin >> n;
	vector<int64_t> x(n), y(n);
	bool zero = true;
	for(int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
		if(x[i] > 0) zero = false;
	}
	ChineseRemainderTheorem<int64_t> crt;
	if(zero) {
		cout << crt.normalisation(x, y, MOD) << '\n';
		return 0;
	}
	try {
		int64_t ans = crt.Garner(x, y, MOD);
		cout << ans << '\n';
	}
	catch(...) {
		cout << -1 << '\n';
	}
	return 0;
}

// int main() {
// 	const int n = 3;
// 	vector<int64_t> x(n), y(n);
// 	for(int i = 0; i < n; ++i) {
// 		cin >> x[i] >> y[i];
// 	}
// 	ChineseRemainderTheorem<int64_t> crt;
// 	try {
// 		int64_t ans = crt.get(x, y);
// 		if(ans == 0) {
// 			ans = 1;
// 			for(int i = 0; i < n; ++i) {
// 				ans = ans * y[i] / crt.exGCD(ans, y[i]);
// 			}
// 		}
// 		cout << ans << '\n';
// 	}
// 	catch(...) {
// 		cout << -1 << '\n';
// 	}
// 	return 0;
// }
0