結果
| 問題 | No.854 公平なりんご分配 |
| ユーザー |
 kotamanegi
|
| 提出日時 | 2019-07-26 21:41:47 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 3,223 bytes |
| コンパイル時間 | 1,312 ms |
| コンパイル使用メモリ | 151,404 KB |
| 実行使用メモリ | 14,008 KB |
| 最終ジャッジ日時 | 2024-05-07 19:14:56 |
| 合計ジャッジ時間 | 11,158 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
ソースコード
#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;
}
}
}