#886987 (C++17) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: Dispersion-atc
• 提出日時: 2023-07-03 20:50:32
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,347 bytes
• コンパイル時間: 1,900 ms
• コンパイル使用メモリ: 201,936 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-24 17:49:27
• 合計ジャッジ時間: 3,133 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,376 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	1 ms; 4,380 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,380 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	1 ms; 4,376 KB
testcase_10	AC	2 ms; 4,376 KB
testcase_11	AC	2 ms; 4,380 KB
testcase_12	AC	1 ms; 4,376 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	2 ms; 4,380 KB
testcase_15	AC	2 ms; 4,380 KB
testcase_16	AC	2 ms; 4,380 KB
testcase_17	AC	1 ms; 4,376 KB
testcase_18	AC	1 ms; 4,376 KB
testcase_19	AC	1 ms; 4,380 KB
testcase_20	AC	2 ms; 4,376 KB
testcase_21	AC	2 ms; 4,376 KB
testcase_22	AC	1 ms; 4,376 KB

ソースコード

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