fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fst first
  6. #define snd second
  7. #define all(c) ((c).begin()), ((c).end())
  8. #define ll int
  9.  
  10. const int INF = 1 << 30;
  11. const int MAXN = 1e5+5;
  12.  
  13. struct Summary {
  14. 	ll gcd;
  15. 	ll cnt;
  16. 	Summary(Summary left, Summary right){
  17. 		gcd = __gcd(left.gcd,right.gcd);
  18. 		cnt = (gcd==left.gcd?left.cnt:0) + (gcd==right.gcd?right.cnt:0);
  19. 	}
  20. 	Summary(ll gcd, ll cnt) : gcd(gcd), cnt(cnt) {}
  21. 	Summary() : gcd(0), cnt(0) {} //elemento neutro
  22. };
  23.  
  24. struct Node {
  25.   Summary value;
  26.   int start, end;
  27.   Node* left;
  28.   Node* right;
  29.  
  30.   Node(int start, int end) : 
  31.     start(start), end(end), value(0,0), left(nullptr), right(nullptr) {}
  32. };
  33.  
  34. Node* build(vector<ll> &arr, int l, int r){
  35.   Node* node = new Node(l,r);
  36.   if(l == r) {
  37.     node->value = Summary(arr[l],1);
  38.     return node;
  39.   }
  40.  
  41.   int m = (l + r) / 2;
  42.   node->left = build(arr, l, m);
  43.   node->right = build(arr, m+1, r);
  44.   node->value = Summary(node->left->value, node->right->value);
  45.   return node;
  46. }
  47.  
  48. Summary query(Node* root, int start, int end) {
  49.   if(start > end) return Summary();
  50.   if(root->start == start && root->end == end)
  51.     return root->value;
  52.  
  53.   int m = (root->start+root->end)/2;
  54.   Summary ans(query(root->left,start,min(m,end)), query(root->right,max(m+1,start),end));
  55.   return ans;
  56. }
  57.  
  58. void solve() {
  59.   int n; cin >> n;
  60.   vector<ll> arr(n);
  61.   for(int i = 0; i < n; i++) {
  62.     cin >> arr[i];
  63.   }
  64.   Node* root = build(arr, 0, n-1);
  65.   int m; cin >> m;
  66.   while(m--) {
  67.     int l,r;
  68.     cin >> l >> r;
  69.     l--,r--;
  70.     Summary ans = query(root, l, r);
  71.     cout << (r - l + 1) - (ans.cnt)  << endl;
  72.   }
  73. }
  74.  
  75. int main() {
  76.   ios::sync_with_stdio(false);
  77.   cin.tie(nullptr);
  78.   int t = 1;
  79.   //cin >> t;
  80.   while(t--)
  81.     solve();
  82. }
  83.  
Success #stdin #stdout 0.01s 5300KB
comments ()
stdin
copy 
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
stdout
copy 
4
4
1
1
https://ideone.com/YIUSGT
language:
C++14 (gcc 8.3)
created:
1 day 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!