結果
問題 | No.854 公平なりんご分配 |
ユーザー |
![]() |
提出日時 | 2019-07-26 21:52:43 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 496 ms / 3,153 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 1,529 ms |
コンパイル使用メモリ | 151,732 KB |
実行使用メモリ | 124,544 KB |
最終ジャッジ日時 | 2024-11-30 14:25:55 |
合計ジャッジ時間 | 12,890 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 92 |
ソースコード
#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; } int sums[100002][310] = {}; int main() { iostream::sync_with_stdio(false); vector<long long> sosuu; for (long long q = 2; q <= 2000; ++q) { int ok = 1; for (long long j = 2; j <= sqrt(q); ++j) { if (q % j == 0) ok = 0; } if (ok == 1) { sosuu.push_back(q); } } long long n; cin >> n; for(int i = 1;i <= n;++i){ long long a; cin >> a; REP(j, sosuu.size()+1) { sums[i][j] = sums[i - 1][j]; } if (a == 0) { sums[i][sosuu.size()]++; continue; } for (int q = 0;q < sosuu.size(); ++q) { while (a % sosuu[q] == 0) { sums[i][q]++; a /= sosuu[q]; } } } int query; cin >> query; REP(i, query) { long long a, b, c; cin >> a >> b >> c; b--; if (sums[c][sosuu.size()] - sums[b][sosuu.size()] >= 1) { cout << "Yes" << endl; continue; } long long ok = 1; for (int q = 0; q < sosuu.size(); ++q) { int cnt = 0; while (a % sosuu[q] == 0) { cnt++; a /= sosuu[q]; } if (sums[c][q] - sums[b][q] < cnt) { ok = 0; break; } } if (a >= 2000) { ok = 0; } if (ok == 1) { cout << "Yes" << endl; } else { cout << "NO" << endl; } } }