Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 10 * 1000 + 10;
- typedef long long ll;
- ll t_gcd[4 * N + 10];
- ll sum[4 * N + 10];
- ll add[4 * N + 10];
- ll a[N];
- ll ans[N];
- vector<int> id[N];
- vector<int> R[N];
- ll gcd(ll a, ll b) {
- while (b != 0) {
- ll t = a;
- a = b;
- b = t % b;
- }
- return a;
- }
- void push(int i, int l, int r) {
- if (l != r) {
- add[2 * i + 1] += add[i];
- add[2 * i + 2] += add[i];
- }
- sum[i] += add[i] * (r - l + 1);
- add[i] = 0;
- }
- ll getSum(int i, int tl, int tr, int l, int r) {
- push(i, tl, tr);
- if (l == tl && r == tr)
- return sum[i];
- int m = (tl + tr) / 2;
- ll sl = 0;
- ll sr = 0;
- if (l <= m)
- sl = getSum(2 * i + 1, tl, m, l, min(r, m));
- if (r > m)
- sr = getSum(2 * i + 2, m + 1, tr, max(m + 1, l), r);
- return sl + sr;
- }
- void makeAdd(int i, int tl, int tr, int l, int r, ll delta) {
- push(i, tl, tr);
- if (l == tl && r == tr) {
- add[i] += delta;
- return;
- }
- int m = (tl + tr) / 2;
- if (l <= m)
- makeAdd(2 * i + 1, tl, m, l, min(r, m), delta);
- if (r > m)
- makeAdd(2 * i + 2, m + 1, tr, max(m + 1, l), r, delta);
- sum[i] = getSum(2 * i + 1, tl, m, tl, m) + getSum(2 * i + 2, m + 1, tr, m + 1, tr);
- }
- void putGcd(int i, int tl, int tr, int pos, ll val) {
- if (tl == tr) {
- t_gcd[i] = val;
- return;
- }
- int m = (tl + tr) / 2;
- if (pos <= m)
- putGcd(2 * i + 1, tl, m, pos, val);
- else
- putGcd(2 * i + 2, m + 1, tr, pos, val);
- t_gcd[i] = gcd(t_gcd[2 * i + 1], t_gcd[2 * i + 2]);
- }
- int getNextPos(int i, int tl, int tr, ll val) {
- if (tl == tr) {
- assert(t_gcd[i] % val != 0);
- return tl;
- }
- int m = (tl + tr) / 2;
- if (t_gcd[2 * i + 1] % val != 0)
- return getNextPos(2 * i + 1, tl, m, val);
- return getNextPos(2 * i + 2, m + 1, tr, val);
- }
- ll getGcd(int i, int tl, int tr, int l, int r) {
- if (l == tl && r == tr)
- return t_gcd[i];
- int m = (tl + tr) / 2;
- ll gl = 0;
- ll gr = 0;
- if (l <= m)
- gl = getGcd(2 * i + 1, tl, m, l, min(r, m));
- if (r > m)
- gr = getGcd(2 * i + 2, m + 1, tr, max(m + 1, l), r);
- return gcd(gl, gr);
- }
- int main() {
- ios_base::sync_with_stdio(0);
- int n;
- cin >> n;
- for (int i = 0; i < n; i++)
- cin >> a[i];
- int q;
- cin >> q;
- for (int i = 0; i < q; i++) {
- int l, r;
- cin >> l >> r;
- l--;
- r--;
- R[l].push_back(r);
- id[l].push_back(i);
- }
- for (int l = n - 1; l >= 0; l--) {
- putGcd(0, 0, n - 1, l, a[l]);
- ll rootGcd = t_gcd[0];
- int r = l;
- while (r < n) {
- ll curGcd = getGcd(0, 0, n - 1, l, r);
- int nextR = n;
- if (curGcd != rootGcd)
- nextR = getNextPos(0, 0, n - 1, curGcd);
- makeAdd(0, 0, n - 1, r, nextR - 1, curGcd);
- r = nextR;
- }
- for (int i = 0; i < R[l].size(); i++)
- ans[id[l][i]] = getSum(0, 0, n - 1, l, R[l][i]);
- }
- for (int i = 0; i < q; i++)
- cout << ans[i] << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment