結果

問題 No.187 中華風 (Hard)
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-10-08 14:51:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,712 bytes
コンパイル時間 2,559 ms
コンパイル使用メモリ 211,996 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-07 00:31:03
合計ジャッジ時間 13,488 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 490 ms
5,248 KB
testcase_03 AC 484 ms
5,248 KB
testcase_04 AC 675 ms
5,248 KB
testcase_05 AC 666 ms
5,248 KB
testcase_06 AC 669 ms
5,248 KB
testcase_07 AC 674 ms
5,248 KB
testcase_08 AC 644 ms
5,248 KB
testcase_09 AC 646 ms
5,248 KB
testcase_10 AC 642 ms
5,248 KB
testcase_11 AC 670 ms
5,248 KB
testcase_12 AC 673 ms
5,248 KB
testcase_13 AC 350 ms
5,248 KB
testcase_14 AC 316 ms
5,248 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 528 ms
5,248 KB
testcase_21 AC 3 ms
5,248 KB
testcase_22 AC 671 ms
5,248 KB
testcase_23 WA -
testcase_24 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

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

////////////////////////////
// 拡張ユークリッドの互除法 //
////////////////////////////

// x, yは非負整数
// ret[0] * x + ret[1] * y == ret[2] == gcd(x, y) となるようなretを返す
std::array<int64_t, 3> extendedEuclidean(const int64_t x, const int64_t y)
{
	if (y == 0) return {1, 0, x};
	auto next{extendedEuclidean(y, x % y)};
	return {next[1], next[0] - (x / y) * next[1], next[2]};
}

/////////////////////////
// Garnerのアルゴリズム //
/////////////////////////

int64_t garner(const std::vector<int64_t>& rests, const std::vector<int64_t>& mods, const int64_t ans_mod)
{
	std::vector<int64_t> coefficient(rests);
	for (int i{}; i < (int)rests.size(); i++)
	{
		int64_t mod_multi{1ll};
		for (int j{}; j < i; j++)
		{
			coefficient[i] = (coefficient[i] + mods[i] - mod_multi * coefficient[j] % mods[i]) % mods[i];
			mod_multi = mod_multi * mods[j] % mods[i];
		}
		for (int j{}; j < i; j++)
			coefficient[i] = coefficient[i] * ((extendedEuclidean(mods[j], mods[i])[0] + mods[i]) % mods[i]) % mods[i];
	}
	int64_t ret{}, mod_multi{1ll};
	for (int i{}; i < (int)rests.size(); i++)
	{
		ret = (ret + mod_multi * coefficient[i] % ans_mod) % ans_mod;
		mod_multi = mod_multi * mods[i] % ans_mod;
	}
	return ret;
}

int64_t solve();
void addMap(std::map<int64_t, std::pair<int, int>>&, int64_t, int, int);

int main()
{
	printf("%lld\n", solve());

	return 0;
}

int64_t solve()
{
	constexpr int64_t mod{1'000'000'007};
	int N;
	scanf("%d", &N);
	std::vector<int64_t> X(N), Y(N);
	for (int i{}; i < N; i++)
		scanf("%lld%lld", &X[i], &Y[i]);
	for (int i{}; i < N; i++)
		for (int j{}; j < N; j++)
		{
			if (i == j) continue;
			const int64_t gcd{calcGCD(Y[i], Y[j])};
			if (X[i] % gcd != X[j] % gcd)
				return -1;
		}
	std::map<int64_t, std::pair<int, int>> primes;
	for (int i{}; i < N; i++)
	{
		int64_t cpy{Y[i]};
		for (int64_t j{2}; j * j <= cpy; j++)
		{
			if (cpy % j > 0) continue;
			int count{};
			while (cpy % j == 0)
			{
				cpy /= j;
				count++;
			}
			addMap(primes, j, count, i);
		}
		if (cpy > 1)
			addMap(primes, cpy, 1, i);
	}
	for (auto& e: primes)
		for (int i{}; i < N; i++)
		{
			if (e.second.second == i) continue;
			while (Y[i] % e.first == 0)
				Y[i] /= e.first;
		}
	for (int i{}; i < N; i++)
		X[i] %= Y[i];

	return std::max(1l, garner(X, Y, mod));
}

void addMap(std::map<int64_t, std::pair<int, int>>& primes, int64_t prime , int count, int index)
{
	auto it{primes.find(prime)};
	if (it == primes.end())
		primes[prime] = {count, index};
	else if (count > it->second.first)
		it->second = {count, index};
}
0