結果
問題 |
No.854 公平なりんご分配
|
ユーザー |
![]() |
提出日時 | 2019-07-26 23:12:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,495 bytes |
コンパイル時間 | 2,445 ms |
コンパイル使用メモリ | 203,368 KB |
最終ジャッジ日時 | 2025-01-07 08:47:04 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 TLE * 37 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> primes; vector<bool> isprime(2000, true); isprime[0] = false; isprime[1] = false; for (int i = 2; i * i < 2000; ++i) { if (isprime[i]) { for (int j = i * i; j < 2000; j += i) { isprime[j] = false; } } } for (int i = 0; i < 2000; ++i) { if (isprime[i]) primes.push_back(i); } int m = primes.size(); vector<vector<int>> ims(n + 1, vector<int>(m)); for (int i = 0; i < n; i++) { ims[i + 1] = ims[i]; int p = a[i]; for (int j = 0; j < m; j++) { while (p % primes[j] == 0) { p /= primes[j]; ++ims[i + 1][j]; } } } int q; cin >> q; for (int i = 0; i < q; i++) { int p, l, r; cin >> p >> l >> r; --l; for (int j = 0; j < m; j++) { int c = ims[r][j] - ims[l][j]; while (p % primes[j] == 0) { p /= primes[j]; --c; } if (c < 0) { p = -1; break; } } if (p != 1) { cout << "NO\n"; } else { cout << "Yes\n"; } } return 0; }