結果

問題 No.854 公平なりんご分配
ユーザー MarcusAureliusAntoninus
提出日時 2019-07-26 22:43:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,750 bytes
コンパイル時間 2,195 ms
コンパイル使用メモリ 203,940 KB
最終ジャッジ日時 2025-01-07 08:23:09
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 43 TLE * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:58:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:63:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |                 scanf("%d", &A);
      |                 ~~~~~^~~~~~~~~~
main.cpp:78:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |         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;

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++)
			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;
	}
	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[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) < count
		)
			return false;
	}
	return P == 1;
}

int main()
{
	scanf("%d", &N);
	makePrimeTable();
	for (int n_i{1}; n_i <= N; n_i++)
	{
		int A;
		scanf("%d", &A);
		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++)
			while (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