結果

問題 No.186 中華風 (Easy)
ユーザー Dispersion-atcDispersion-atc
提出日時 2023-07-03 20:48:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,334 bytes
コンパイル時間 1,574 ms
コンパイル使用メモリ 170,160 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-17 18:41:51
合計ジャッジ時間 2,387 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 1 ms
6,948 KB
testcase_22 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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 (m == -1) {cout << -1 << endl;}
	else {cout << r << " " << m << endl;}
	
	return 0;
}
0