結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー MarcusAureliusAntoninus
提出日時 2019-10-08 14:44:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 277 ms / 3,000 ms
コード長 2,665 bytes
コンパイル時間 2,434 ms
コンパイル使用メモリ 207,668 KB
最終ジャッジ日時 2025-01-07 21:18:42
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

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;
}

int main()
{
	using namespace std;
	using ll = int64_t;
	int n;
	cin >> n;
	vector<ll> vs(n), ms(n);
	for (int i = 0; i < n; i++)
	{
		cin >> vs[i] >> ms[i];
	}

	vector<int> primes;
	for (int i = 2; (ll)i * i <= 1e9; i++)
	{
		int flag = 1;
		for (int x : primes)
			if (i % x == 0)
			{
				flag = 0;
				break;
			}
		if (flag)
			primes.emplace_back(i);
	}

	for (int m : ms)
	{
		for (int p : primes)
			while (m % p == 0)
				m /= p;
		if (m != 1)
			primes.emplace_back(m);
	}

	for (int p : primes)
	{
		vector<pair<int, int>> ps;
		for (int i = 0; i < n; i++)
		{
			if (ms[i] % p == 0)
			{
				int lg = 0;
				while (ms[i] % p == 0)
					ms[i] /= p, lg++;
				ps.emplace_back(lg, i);
			}
		}
		if (ps.size() < 1)
			continue;
		sort(begin(ps), end(ps));
		int base = vs[ps.back().second];
		for (auto d : ps)
		{
			if (vs[d.second] % p != base % p)
			{
				cout << -1 << endl;
				return 0;
			}
			if (d.second == ps.back().second)
			{
				for (int i = 0; i < d.first; i++)
					ms[d.second] *= p;
			}
		}
	}

	int allzero = 1;
	ll ans = 1;
	for (int i = 0; i < n; i++)
	{
		vs[i] = vs[i] % ms[i];
		if (vs[i] != 0)
			allzero = 0;
		ans = ans * ms[i] % int(1e9 + 7);
	}
	if (allzero)
	{
		cout << ans << endl;
		return 0;
	}

	cout << garner(vs, ms, 1e9 + 7) << endl;
}
0