結果

問題 No.186 中華風 (Easy)
ユーザー pazzle1230pazzle1230
提出日時 2019-08-10 03:44:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,375 bytes
コンパイル時間 1,782 ms
コンパイル使用メモリ 170,976 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-27 00:56:06
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

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

ソースコード

diff #

#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 (-1, -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(-1, -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;
	}
}
0