結果

問題 No.854 公平なりんご分配
ユーザー kotamanegikotamanegi
提出日時 2019-07-26 21:41:47
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,223 bytes
コンパイル時間 1,366 ms
コンパイル使用メモリ 150,268 KB
実行使用メモリ 915,456 KB
最終ジャッジ日時 2024-11-30 14:23:48
合計ジャッジ時間 377,845 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
10,496 KB
testcase_01 TLE -
testcase_02 TLE -
testcase_03 WA -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 AC 17 ms
12,064 KB
testcase_07 MLE -
testcase_08 WA -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 WA -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 WA -
testcase_15 WA -
testcase_16 MLE -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 26 ms
285,440 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 TLE -
testcase_33 WA -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 WA -
testcase_37 MLE -
testcase_38 MLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 MLE -
testcase_42 TLE -
testcase_43 TLE -
testcase_44 TLE -
testcase_45 TLE -
testcase_46 TLE -
testcase_47 TLE -
testcase_48 MLE -
testcase_49 MLE -
testcase_50 MLE -
testcase_51 MLE -
testcase_52 WA -
testcase_53 WA -
testcase_54 TLE -
testcase_55 TLE -
testcase_56 TLE -
testcase_57 WA -
testcase_58 TLE -
testcase_59 WA -
testcase_60 TLE -
testcase_61 WA -
testcase_62 TLE -
testcase_63 TLE -
testcase_64 WA -
testcase_65 TLE -
testcase_66 TLE -
testcase_67 TLE -
testcase_68 WA -
testcase_69 TLE -
testcase_70 WA -
testcase_71 TLE -
testcase_72 TLE -
testcase_73 TLE -
testcase_74 TLE -
testcase_75 TLE -
testcase_76 TLE -
testcase_77 TLE -
testcase_78 TLE -
testcase_79 TLE -
testcase_80 TLE -
testcase_81 TLE -
testcase_82 TLE -
testcase_83 RE -
testcase_84 RE -
testcase_85 RE -
testcase_86 RE -
testcase_87 RE -
testcase_88 RE -
testcase_89 RE -
testcase_90 RE -
testcase_91 RE -
testcase_92 RE -
testcase_93 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<complex<double>>  DFT(vector<complex<double>> a) {
	int n = a.size();
	if (n == 1) return a;
	vector<complex<double>> a0(n / 2), a1(n / 2);
	REP(i, n) {
		if (i % 2 == 0) {
			a0[i / 2] = a[i];
		}
		else {
			a1[i / 2] = a[i];
		}
	}
	vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1);
	vector<complex<double>> inversed_a(n);
	for (int i = 0; i < n; ++i) {
		complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n));
		inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)];
	}
	return inversed_a;
}
vector<complex<double>> IDFT(vector<complex<double>> inversed_a) {
	int n = inversed_a.size();
	vector<complex<double>> now = DFT(inversed_a);
	reverse(now.begin(), now.end());
	for (int q = now.size() - 1; q >= 1; --q) {
		swap(now[q], now[q - 1]);
	}
	REP(i, n) {
		now[i] /= complex<double>(n, 0);
	}
	return now;
}
vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) {
	int deg = a.size() + b.size() - 1;
	int n = 1;
	while (n < deg) n <<= 1;
	a.resize(n);
	b.resize(n);
	vector<complex<double>> inversed_a = DFT(a), inversed_b = DFT(b);
	vector<complex<double>> inversed_c(n);
	REP(i, n) {
		inversed_c[i] = inversed_a[i] * inversed_b[i];
	}
	return IDFT(inversed_c);
}
long long inv(long long now) {
	long long hoge = MOD - 2LL;
	long long ans = 1;
	while (hoge != 0) {
		if (hoge % 2 == 1) {
			ans *= now;
			ans %= MOD;
		}
		hoge /= 2;
		now *= now;
		now %= MOD;
	}
	return ans;
}
long long sums[100001][3001] = {};
int main() {
	iostream::sync_with_stdio(false);
	long long n;
	cin >> n;
	for(int i = 1;i <= n;++i){
		long long a;
		cin >> a;
		REP(j, 3001) {
			sums[i][j] = sums[i - 1][j];
		}
		for (int q = 2; q <= sqrt(a); ++q) {
			while (a % q == 0) {
				sums[i][q]++;
				a /= q;
			}
		}
		sums[i][a]++;
	}
	int query;
	cin >> query;
	REP(i, query) {
		long long a, b, c;
		cin >> a >> b >> c;
		a -= 2;
		b--;
		if (sums[b][0] - sums[a][0] >= 1) {
			cout << "Yes" << endl;
			continue;
		}
		long long ok = 1;
		for (int q = 2; q <= 3000; ++q) {
			int cnt = 0;
			while (c % q == 0) {
				c /= q;
				cnt++;
			}
			if (sums[b][q] - sums[a][q] < cnt) {
				ok = 0;
				break;
			}
		}
		if (c >= 3000) {
			ok = 0;
		}
		if (ok == 1) {
			cout << "Yes" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
}
0