結果

問題 No.854 公平なりんご分配
ユーザー MarcusAureliusAntoninus
提出日時 2019-07-26 23:00:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 2,392 ms
コンパイル使用メモリ 204,160 KB
最終ジャッジ日時 2025-01-07 08:33:18
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 56 WA * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘bool dividable()’:
main.cpp:28:19: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   28 |         scanf("%lld%d%d", &P, &L, &R);
      |                ~~~^       ~~
      |                   |       |
      |                   |       int64_t* {aka long int*}
      |                   long long int*
      |                %ld
main.cpp:28:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |         scanf("%lld%d%d", &P, &L, &R);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:59:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:65:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |                 scanf("%d", &A);
      |                 ~~~~~^~~~~~~~~~
main.cpp:86:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using vi = std::vector<int64_t>;
using vvi = std::vector<vi>;

int N;
vvi smallPrime, largePrime;
vi primeTable, zeroCount;

void makePrimeTable()
{
	std::vector<bool> isPrime(2'001, true);
	for (int i{2}; i <= 2'000; i++)
	{
		if (!isPrime[i]) continue;
		primeTable.push_back(i);
		if (i <= 100) smallPrime.push_back(vi(N + 1));
		else largePrime.push_back({});
		for (int j{2 * i}; j <= 2'000; j += i)
			isPrime[j] = false;
	}
}

bool dividable()
{
	int64_t P;
	int L, R;
	scanf("%lld%d%d", &P, &L, &R);
	L--;
	for (int p_i{}; p_i < (int)smallPrime.size() && P > 1; p_i++)
	{
		int count{};
		while (P % primeTable[p_i] == 0)
		{
			P /= primeTable[p_i];
			count++;
		}
		if (count > smallPrime[p_i][R] - smallPrime[p_i][L]) return false;
	}
	if (P == 1) return true;
	for (int p_i{}; p_i < (int)largePrime.size() && P > 1; p_i++)
	{
		int count{};
		while (P % primeTable[smallPrime.size() + p_i] == 0)
		{
			P /= primeTable[smallPrime.size() + p_i];
			count++;
		}
		if (count > 0 &&
			std::upper_bound(largePrime[p_i].begin(), largePrime[p_i].end(), R) - std::lower_bound(largePrime[p_i].begin(), largePrime[p_i].end(), L + 1) < count
		)
			return false;
	}
	return P == 1;
}

int main()
{
	scanf("%d", &N);
	makePrimeTable();
	zeroCount.resize(N + 1);
	for (int n_i{1}; n_i <= N; n_i++)
	{
		int A;
		scanf("%d", &A);
		zeroCount[n_i] += zeroCount[n_i - 1];
		if (A == 0)
		{
			zeroCount[n_i]++;
			continue;
		}
		for (int p_i{}; p_i < (int)smallPrime.size(); p_i++)
		{
			while (A % primeTable[p_i] == 0)
			{
				A /= primeTable[p_i];
				smallPrime[p_i][n_i]++;
			}
			smallPrime[p_i][n_i] += smallPrime[p_i][n_i - 1];
		}
		for (int p_i{}; p_i < (int)largePrime.size(); p_i++)
			if (A % primeTable[smallPrime.size() + p_i] == 0)
				largePrime[p_i].push_back(n_i);
	}
	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
		if (dividable()) puts("Yes");
		else puts("NO");

	return 0;
}
0