fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pii pair<int, int>
  6. #define pll pair<long long, long long>
  7. #define pb push_back
  8. #define ff first
  9. #define ss second
  10. #define YES cout << "YES\n"
  11. #define NO cout << "NO\n"
  12. #define nn "\n"
  13. #define sci(x) scanf("%d", &x)
  14. #define LL_INF (1LL << 62)
  15. #define INF (1 << 30)
  16. #define SetBit(x, k) (x |= (1LL << k))
  17. #define ClearBit(x, k) (x &= ~(1LL << k))
  18. #define CheckBit(x, k) (!!(x & (1LL << k)))
  19. #define mod 1000000007
  20. #define N 100006
  21.  
  22. int x[N];
  23. vector<int> p[N];
  24. vector<int> d[N];
  25. int l, r, z;
  26. vector<int> fact;
  27. int dp[1<<6];
  28.  
  29. int solve(int mask, int sz){
  30.     if(mask==0) return l-2;
  31.  
  32.     if(dp[mask] != -1) return dp[mask];
  33.  
  34.     int res = INF;
  35.     for(int i = 0; i < sz; i++){
  36.         if(mask & (1<<i)){
  37.             int pos = solve(mask ^ (1<<i), sz);
  38.             if(pos == INF) continue;
  39.             if(pos >= l && x[pos]%fact[i]==0) res = min(res, pos);
  40.             else {
  41.                 int nxt = *upper_bound(d[fact[i]].begin(), d[fact[i]].end(), pos+1);
  42.                 res = min(res, nxt);
  43.             }
  44.         }
  45.     }
  46.  
  47.     return dp[mask] = res;
  48. }
  49.  
  50.  
  51. int main(){
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(0);
  54.  
  55.     // freopen("input.txt", "r", stdin);
  56.     // freopen("output-01.txt", "w", stdout);
  57.  
  58.     for(int i = 2; i < N; i++){
  59.         if(!p[i].empty()) continue;
  60.         for(int j = i; j < N; j += i){
  61.             p[j].pb(i);
  62.         }
  63.     }
  64.  
  65.     int n, q;
  66.     cin >> n >> q;
  67.  
  68.     for(int i = 1; i <= n; i++){
  69.         cin >> x[i];
  70.         for(int prime: p[x[i]]){
  71.             int c = 1;
  72.             int v = x[i];
  73.             while(v%prime==0){
  74.                 v /= prime;
  75.                 c *= prime;
  76.                 d[c].pb(i);
  77.             }
  78.         }
  79.     }
  80.  
  81.     for(int i = 0; i < N; i++){
  82.         d[i].pb(INF);
  83.     }
  84.  
  85.     while(q--){
  86.         fact.clear();
  87.         memset(dp, -1, sizeof dp);
  88.  
  89.         cin >> l >> r >> z;
  90.  
  91.         for(int prime: p[z]){
  92.             int c = 1;
  93.             int v = z;
  94.             while(v%prime==0){
  95.                 v /= prime;
  96.                 c *= prime;
  97.             }
  98.             fact.pb(c);
  99.         }
  100.  
  101.         int sz = fact.size();
  102.         int rx = max(l, solve((1<<sz)-1, sz));
  103.  
  104.         if(rx <= r) cout << "Yes\n";
  105.         else cout << "No\n";
  106.     }
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0.02s 14812KB
comments (?)
stdin
copy 
6 5
4 7 3 5 12 22
1 5 10
2 5 10
5 5 12
3 5 10
1 4 20
stdout
copy 
Yes
No
Yes
No
Yes
https://ideone.com/KGlyls
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!