結果

問題 No.187 中華風 (Hard)
ユーザー MarcusAureliusAntoninus
提出日時 2019-10-08 14:06:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,688 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 205,128 KB
最終ジャッジ日時 2025-01-07 21:18:05
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:58:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
   58 |         printf("%lld\n", solve());
      |                 ~~~^     ~~~~~~~
      |                    |          |
      |                    |          int64_t {aka long int}
      |                    long long int
      |                 %ld
main.cpp: In function ‘int64_t solve()’:
main.cpp:70:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type*’ {aka ‘long int*’} [-Wformat=]
   70 |                 scanf("%lld%lld", &X[i], &Y[i]);
      |                        ~~~^
      |                           |
      |                           long long int*
      |                        %ld
main.cpp:70:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type*’ {aka ‘long int*’} [-Wformat=]
   70 |                 scanf("%lld%lld", &X[i], &Y[i]);
      |                            ~~~^
      |                               |
      |                               long long int*
      |                            %ld
main.cpp:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |                 scanf("%lld%lld", &X[i], &Y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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