結果

問題 No.186 中華風 (Easy)
ユーザー Dispersion-atc
提出日時 2023-07-03 20:50:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,347 bytes
コンパイル時間 2,071 ms
コンパイル使用メモリ 195,476 KB
最終ジャッジ日時 2025-02-15 05:41:07
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// ax + by = gcd(a, b) を満たす、(x, y) を求める。返り値は gcd(a, b)
// x, y の最小性は保証しない
long long ext_gcd(long long a, long long b, long long &x, long long &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	
	long long g = ext_gcd(b, a % b, y, x);
	y -= a / b * x;
	
	return g;
}

// r1 (mod m1) かつ r2 (mod m2) -> r (mod m)
// のとき、(r, m) を返す。解なし (矛盾) ならば、(r, m) = (0, -1)
pair<long long, long long> chinese_reminder(long long r1, long long m1, long long r2, long long m2)
{
	long long x, y;
	long long g = ext_gcd(m1, m2, x, y);
	if ((r2 - r1) % g != 0) {return make_pair(0, -1);}
	
	// m1 * x + m2 * y = g を満たす
	// r = r1 + m1 * k1 = r2 + m2 * k2, k1 = 0 ~ m2 / g, k2 = 0 ~ m1 / g
	// -> m1 * k1 + m2 * (-k2) = r2 - r1 より、k1 = x * (r2 - r1) / g
	long long m = m1 / g * m2;
	x %= (m2 / g);
	long long k1 = (r2 - r1) / g * x % (m2 / g);
	long long r = ((r1 + m1 * k1) % m + m) % m;
	return make_pair(r, m);
}


/*-- main --*/



int main()
{
	long long r = 0, m = 1;
	
	for (int i = 0; i < 3; ++i)
	{
		long long x, y; cin >> x >> y;
		tie(r, m) = chinese_reminder(r, m, x, y);
		if (m == -1) {break;}
	}
	
	if (r == 0) {r += m;}
	
	if (m == -1) {cout << -1 << endl;}
	else {cout << r << endl;}
	
	return 0;
}
0