結果

問題 No.187 中華風 (Hard)
ユーザー Tlapesium
提出日時 2021-03-09 00:54:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 158 ms / 3,000 ms
コード長 1,979 bytes
コンパイル時間 3,526 ms
コンパイル使用メモリ 218,828 KB
最終ジャッジ日時 2025-01-19 13:00:02
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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