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

• 問題: No.186 中華風 (Easy)
• ユーザー: _dehachi
• 提出日時: 2023-01-26 22:11:50
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 888 bytes
• コンパイル時間: 2,367 ms
• コンパイル使用メモリ: 209,792 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-27 13:05:30
• 合計ジャッジ時間: 3,227 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

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

ソースコード

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

template <typename T>
struct CRT {
	T rem, mod;
	CRT(): rem(0), mod(1) {}
	void add(T r, T m) {
		auto ext_gcd = [](T a, T b, T &x, T &y, T &d) -> void {
			x = 1, y = 0;
			T u = 0, v = 1;
			while (b) {
				T p = a/b, q = a%b, r = x-u*p;
				x = u, u = r;
				r = y-v*p;
				y = v, v = r;
				a = b, b = q;
			}
			d = a;
		};
		T p, q, d;
		ext_gcd(mod, m, p, q, d);
		if ((r-rem)%d != 0) {
			rem = mod = 0;
			return;
		}
		rem += mod*((r-rem)/d*p%(m/d));
		mod *= m/d;
	}
	pair<T,T> get() {return {rem<0?rem+mod:rem, mod};}
};

void solve() {
	CRT<ll> crt;
	for (int i=0; i<3; i++) {
		ll x, y;
		cin >> x >> y;
		crt.add(x, y);
	}
	auto [r, m] = crt.get();
	cout << (m?r?r:r+m:-1) << '\n';
}

signed main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	solve();
	return 0;
}