#626894 (C++17) No.187 中華風 (Hard)

• 問題: No.187 中華風 (Hard)
• ユーザー: Tlapesium
• 提出日時: 2021-03-09 00:54:36
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 118 ms / 3,000 ms
• コード長: 1,979 bytes
• コンパイル時間: 2,616 ms
• コンパイル使用メモリ: 214,560 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-18 21:40:54
• 合計ジャッジ時間: 5,210 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	99 ms; 5,376 KB
testcase_03	AC	98 ms; 5,376 KB
testcase_04	AC	117 ms; 5,376 KB
testcase_05	AC	118 ms; 5,376 KB
testcase_06	AC	115 ms; 5,376 KB
testcase_07	AC	118 ms; 5,376 KB
testcase_08	AC	100 ms; 5,376 KB
testcase_09	AC	99 ms; 5,376 KB
testcase_10	AC	99 ms; 5,376 KB
testcase_11	AC	114 ms; 5,376 KB
testcase_12	AC	114 ms; 5,376 KB
testcase_13	AC	49 ms; 5,376 KB
testcase_14	AC	48 ms; 5,376 KB
testcase_15	AC	99 ms; 5,376 KB
testcase_16	AC	98 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	87 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	114 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


auto extGCD(long long a, long long b) {
	long long x = 1, y = 0, u = 0, v = 1;
	while (b != 0) {
		auto j = a % b, k = a / b;
		x -= k * u; y -= k * v;
		std::swap(x, u); std::swap(y, v);
		a = b; b = j;
	}
	return std::make_pair(x, y);
}

long long crt(std::vector<long long>& b, std::vector<long long>& m, long long mod = std::numeric_limits<long long>::max()) {
	auto pmod = [&](long long a, long long m) {
		a = a % m;
		return (a < 0 ? a + m : a);
	};
	auto modinv = [&](long long a, long long m) {
		auto [x, y] = extGCD(a, m);
		return pmod(x, m);
	};
	for (int i = 0; i < b.size(); i++) {
		for (int j = 0; j < i; j++) {
			long long g = gcd(m[i], m[j]);
			if ((b[i] - b[j]) % g != 0)return -1;
			m[i] /= g; m[j] /= g;
			long long 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];
		}
	}
	m.push_back(mod);
	std::vector<long long> tmp1(m.size(), 1), tmp2(m.size(), 0);
	for (int k = 0; k < b.size(); k++) {
		long long t = pmod((b[k] - tmp2[k]) * modinv(tmp1[k], m[k]), m[k]);
		for (int i = k + 1; i < m.size(); i++) {
			tmp2[i] = (tmp2[i] + tmp1[i] * t) % m[i];
			tmp1[i] = (tmp1[i] * m[k]) % m[i];
		}
	}
	return tmp2.back();
}

int main() {
	int N;
	cin >> N;
	bool flag = false;
	vector<ll> b(N), m(N);
	for (int i = 0; i < N; i++) {
		cin >> b[i] >> m[i];
		if (b[i])flag = true;
	}
	ll ans = crt(b, m, MOD);
	if (ans != -1 && !flag) {
		ans = 1;
		for (int i = 0; i < N; i++)ans = (ans * m[i]) % MOD;
	}
	cout << ans << endl;
}