1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <bits/stdc++.h> using namespace std; using PII = pair<int, int>; vector<int> v; struct Node{ int gcd, cnt; Node *lc, *rc; Node(): gcd(0), cnt(0), lc(nullptr), rc(nullptr){}; void pull() { gcd = __gcd(lc->gcd, rc->gcd); if(lc->gcd == gcd) { cnt += lc->cnt; } if(rc->gcd == gcd) { cnt += rc->cnt; } } };
Node *build(int L, int R) { Node *node = new Node(); if(L == R) { node->gcd = v[L]; node->cnt = 1; return node; } int M = (L + R) >> 1; node->lc = build(L, M); node->rc = build(M + 1, R); node->pull(); return node; }
PII query(Node *node, int L, int R, int qL, int qR) { if(qL <= L && R <= qR) { return {node->gcd, node->cnt}; } int M = (L + R) >> 1; if(qR <= M) { return query(node->lc, L, M, qL, qR); } else if (M < qL) { return query(node->rc, M + 1, R, qL, qR); } else { auto lhs = query(node->lc, L, M, qL, qR); auto rhs = query(node->rc, M + 1, R, qL, qR); int gcd = __gcd(lhs.first, rhs.first), cnt = 0; if(lhs.first == gcd) { cnt += lhs.second; } if(rhs.first == gcd) { cnt += rhs.second; } return {gcd, cnt}; } }
int main() { int n, q; cin >> n; v.resize(n + 5); for(int i = 1; i <= n; ++i) { cin >> v[i]; } Node *root = build(1, n); cin >> q; for(int i = 0, x, y; i != q; ++i) { cin >> x >> y; cout << y - x + 1 - query(root, 1, n, x, y).second << '\n'; } }
|