#367458 (C++14) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: pazzle1230
• 提出日時: 2019-08-10 03:42:52
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 2,373 bytes
• コンパイル時間: 1,503 ms
• コンパイル使用メモリ: 172,628 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-19 16:55:28
• 合計ジャッジ時間: 2,204 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	WA	-
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	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-

ソースコード

#include <bits/stdc++.h>

::std::int64_t gcd(::std::int64_t a, ::std::int64_t b) {
	while (b != 0) {
		::std::swap(a, b);
		b = b % a;
	}
	return a;
}

::std::int64_t lcm(::std::int64_t a, ::std::int64_t b) {
	return a / gcd(a, b) * b;
}

::std::pair<::std::int64_t, ::std::int64_t> extgcd(::std::int64_t a, ::std::int64_t b) {
	::std::pair<::std::int64_t, ::std::int64_t> pa(1, 0), pb(0, 1);
	while (b != 0) {
		::std::swap(a, b); ::std::swap(pa, pb);
		pb = ::std::make_pair(pb.first - pa.first * (b / a), pb.second - pa.second * (b / a));
		b = b % a;
	}
	return pa;
}


// return x (mod lcm(m_i)) and lcm(m_i) that satisfies x ≡ b_i (mod m_i) (中国剰余定理)
// if there isn't the answer, return (0, -1)
// O(N log M)
::std::pair<::std::int64_t, ::std::int64_t> CRT(const ::std::vector<::std::int64_t> &b, ::std::vector<::std::int64_t> &m) {
	::std::int64_t ret = 0, M = 1;
	for (::std::size_t i = 0; i < b.size(); ++i) {
		::std::int64_t p, q;
		::std::int64_t d = gcd(M, m[i]);
		::std::tie(p, q) = extgcd(M, m[i]);
		if ((b[i] - ret) % d != 0) return ::std::make_pair(0, -1);
		::std::int64_t tmp = (b[i] - ret) / d * p % (m[i] / d);
		ret += M * tmp;
		M *= m[i] / d;
	}
	return ::std::make_pair((ret + M) % M, M);
}

// return x mod MOD
// It must be guranteed that all elements of m are coprime
// O(N^2)
std::int64_t garner(const std::vector<std::int64_t>& b, const std::vector<std::int64_t>& m, const std::int64_t MOD) {
	std::vector<std::int64_t> coeffs(b.size()+1, 1); 
	std::vector<std::int64_t> constants(b.size()+1, 0); 
	for (int i = 0; i < b.size(); ++i) {
		std::int64_t p, inv;
		std::tie(inv, p) = extgcd(coeffs[i], m[i]);
		std::int64_t t = (b[i] - constants[i]) * inv % m[i];
		if (t < 0) t += m[i];
		if ((coeffs[i] * t + constants[i]) % m[i] != b[i]) return -1;
		for (int j = i+1; j < b.size(); ++j) {
			constants[j] = (constants[j] + coeffs[j] * t) % m[j];
			coeffs[j] = (coeffs[j] * m[i]) % m[j];
		}
		constants.back() = (constants.back() + coeffs.back() * t) % MOD;
		coeffs.back() = (coeffs.back() * m[i]) % MOD;
	}
	return constants.back();
}

int main(void) {
	using namespace std;
	vector<int64_t> x(3), y(3);
	int64_t l = 1;
	bool all0 = 1;
	for (int i = 0; i < 3; i++) {
		cin >> x[i] >> y[i];
		if (x[i] != 0) all0 = 0;
		l = lcm(l, y[i]);
	}
	if (all0) {
		cout << l << endl;
	} else {
		cout << CRT(x, y).first << endl;
	}
}