結果

問題 No.187 中華風 (Hard)
ユーザー ooaiu
提出日時 2025-02-25 16:48:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 291 ms / 3,000 ms
コード長 2,605 bytes
コンパイル時間 4,277 ms
コンパイル使用メモリ 294,480 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-25 16:48:25
合計ジャッジ時間 9,211 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) (void(0))
#endif
void run_case();
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) run_case();
	return 0;
}
pair<ll, ll> ext_gcd(ll a, ll b) {
	if(b == 0) return {1, 0};
	pair<ll, ll> e = ext_gcd(b, a % b);
	return {e.second, e.first - (a/b) * e.second};
}
ll inv(ll p, ll q) {
	auto e = ext_gcd(p, q);
	return (e.first % q + q) % q;
}
vector<ll> Garner(const vector<ll>& a, const vector<ll>& b) {
	assert(a.size() == b.size());
	vector<ll> x(a.size());
	const int N = a.size();
	for(int i = 0; i < N; i++) {
		x[i] = a[i];
		for(int j = 0; j < i; j++) {
			x[i] = (x[i] - x[j]) * inv(b[j], b[i]);
			x[i] %= b[i];
			if(x[i] < 0) {
				x[i] += b[i];
			}
		}
	}
	return x;
}
vector<pair<int, int>> factor(int x) {
	vector<pair<int, int>> ret;
	if(x % 2 == 0) {
		ret.push_back({2, 0});
		while(x % 2 == 0) {
			ret.back().second++;
			x /= 2;
		}
	}
	for(int d = 3; d * d <= x; d+=2) {
		if(x % d == 0) {
			ret.push_back({d, 0});
			while(x % d == 0) {
				ret.back().second++;
				x /= d;
			}
		}
	}
	if(x != 1) ret.push_back({x, 1});
	return ret;
}
int mpow(int a, int b) {
	int r = 1;
	for(;b;b>>=1,a*=a)if(b&1)r*=a;
	return r;
}
const int MOD = 1e9 + 7;
int N;
int X[1010], Y[1010];
void run_case() {
	cin >> N;
	vector<ll> NX, NY;
	{
		for(int i = 0; i < N; i++) cin >> X[i] >> Y[i];
		vector<int> old_X;
		struct num {
			int p; int cn; int val;
		};
		vector<num> old_Y;
		for(int i = 0; i < N; i++) {
			auto f = factor(Y[i]);
			for(const auto&[p,cn]: f) {
				old_X.push_back(X[i]);
				old_Y.push_back({p, cn, mpow(p, cn)});
			}
		}
		const int M = old_X.size();
		map<int, pair<int, int>> mx;
		for(int i = 0; i < M; i++) {
			for(int j = i + 1; j < M; j++) if(old_Y[i].p == old_Y[j].p) {
				int g = min(old_Y[i].cn, old_Y[j].cn);
				int pwg = mpow(old_Y[i].p, g);
				if(old_X[i] % pwg != old_X[j] % pwg) {
					cout << -1 << "\n";
					return;
				}
			}
			mx[old_Y[i].p] = max(mx[old_Y[i].p], {old_Y[i].val, old_X[i]});
		}
		for(const auto&[val, x] : mx) {
			NX.push_back(x.second % x.first);
			NY.push_back(x.first);
		}
	}
	debug(NX, NY);
	auto T = Garner(NX, NY);
	if(T == vector<ll>(T.size(), 0)) {
		ll ans = 1;
		for(int i = 0; i < T.size(); i++) ans = (ans * NY[i]) % MOD;
		cout << ans << endl;
	} else {
		ll prod = 1;
		ll ans = 0;
		for(int i = 0; i < T.size(); i++) {
			ans += T[i] * prod;
			prod *= NY[i];
			ans %= MOD;
			prod %= MOD;
		}
		cout << ans << endl;
	}
}
0