結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー idat_50me
提出日時 2023-10-08 17:56:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 120 ms / 3,000 ms
コード長 2,334 bytes
コンパイル時間 1,782 ms
コンパイル使用メモリ 198,856 KB
最終ジャッジ日時 2025-02-17 06:18:17
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/187

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

long long extgcd(long long a, long long b, long long &x, long long &y) {
	long long x_ = abs(a), xd = 1, xdd = 0, y_ = abs(b), yd = 0, ydd = 1, div;
	while(true) {
		if(!y_) {
			x = xd;
			y = xdd;
			return x_;
		}
		div = x_ / y_;
		x_ -= div * y_;
		xd -= div * yd;
		xdd -= div * ydd;

		if(!x_) {
			x = yd;
			y = ydd;
			return y_;
		}
		div = y_ / x_;
		y_ -= div * x_;
		yd -= div * xd;
		ydd -= div * xdd;
	}
	if(a < 0) x = -x;
	if(b < 0) y = -y;
}

long long extgcd(long long a, long long b, long long c, long long &x, long long &y) {
	long long d = extgcd(a, b, x, y);
	if(c % d) return -1;
	if(a != 0) {
		x *= c % a / d;
		y *= c % a / d;
		x += c / a;
	}
	return d;
}

long long pregarner(vector<long long> &B, vector<long long> &M, const int p) {
	long long lcm = 1, g, gi, gj;
	for(int i = 0; i < M.size(); i++) {
		for(int j = i + 1; j < M.size(); j++) {
			g = gcd(M[i], M[j]);
			if((B[j] - B[i]) % g) return -1;

			M[i] /= g, M[j] /= g;
			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];
		}
		(lcm *= M[i]) %= p;
	}
	return lcm;
}

long long garner(const vector<long long> &B, const vector<long long> &M, const int p) {
	const int n = M.size();
	vector<long long> mprod(n + 1, 1);
	vector<long long> X(n + 1, 0);
	long long t, x, y, inv;

	for(int k = 0; k < n; k++) {
		if(extgcd(mprod[k], M[k], 1, x, y) == -1) return -1;
		inv = x % M[k];
		if(inv < 0) inv += M[k];
		t = (B[k] - X[k]) * inv % M[k];
		if(t < 0) t += M[k];
		for(int i = k + 1; i < n; i++) {
			(X[i] += t * mprod[i]) %= M[i];
			(mprod[i] *= M[k]) %= M[i];
		}
		(X[n] += t * mprod[n]) %= p;
		(mprod[n] *= M[k]) %= p;
	}
	return X.back();
}


constexpr int MPRIME = 1000000007;

int main() {
	int N;
	vector<long long> X, Y;
	bool zr = true;

	cin >> N;
	X.resize(N);
	Y.resize(N);
	for(int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
		if(X[i]) zr = false;
	}

	long long lcm = pregarner(X, Y, MPRIME);
	if(lcm == -1) {
		cout << -1 << endl;
		return 0;
	}

	long long ans = garner(X, Y, MPRIME);
	if(zr) cout << lcm << endl;
	else
		cout << ans << endl;
}
0