fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using ull = unsigned long long;
  6.  
  7. const int N = 70005;
  8.  
  9. int n, q;
  10.  
  11. int spf[N];
  12. vector<int> primes;
  13. ull P[N], H[N], mask[N];
  14.  
  15. void precompute() {
  16.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  17.     for (int i = 2; i < N; i++) {
  18.         if (!spf[i]) {
  19.             spf[i] = i;
  20.             primes.push_back(i);
  21.             H[i] = rng();
  22.         }
  23.         for (int p : primes) {
  24.             if (p > spf[i] || i * p >= N) break;
  25.             spf[i * p] = p;
  26.         }
  27.     }
  28.     for (int i = 2; i < N; i++) mask[i] = mask[i / spf[i]] ^ H[spf[i]];
  29. }
  30.  
  31. void solve() {
  32.     cin >> n >> q;
  33.     for (int i = 1; i <= n; i++) {
  34.         int x; cin >> x;
  35.         P[i] = P[i - 1] ^ mask[x];
  36.     }
  37.     while (q--) {
  38.         int l, r; cin >> l >> r;
  39.         if (P[r] == P[l - 1]) cout << "YES\n";
  40.         else cout << "NO\n";
  41.     }
  42. }
  43.  
  44. int main() {
  45.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  46.  
  47.     #define TASK "SEQCP"
  48.     if (fopen(TASK".INP", "r")) {
  49.         freopen(TASK".INP", "r", stdin);
  50.         freopen(TASK".OUT", "w", stdout);
  51.     }
  52.  
  53.     precompute();
  54.  
  55.     int tests = 1; // cin >> tests;
  56.     while (tests--) solve();
  57.  
  58.     #ifdef LOCAL
  59.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  60.     #endif
  61.     return 0;
  62. };
  63.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5 3
2 4 8 16 32
1 3
2 4
1 5
stdout
copy 
YES
NO
NO
https://ideone.com/o4lPfq
Chọn Đội tuyển HSGQG Bắc Ninh 2025 - Đoạn con chính phương
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!