1497.cpp

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define fo(i, n) for(int i = 1; i <= n; ++i)

typedef long long ll;

const int N = 1000300;
const int mod = 1e9 + 7;

int lp[N];
int l[200200], r[200200];
int a[200200], n, q;
int ans[200200];
int cnt[N];
int X[N];
vector<int> e[200200];

inline void sieve() {
    for(int i = 2; i <= 1000000; ++i) {
        if(!lp[i]) {
            lp[i] = i;
            if(i * 1ll * i <= 1000000)
                for(int j = i * i; j <= 1000000; j += i)
                    lp[j] = i;
        }
    }
}
vector<pair<int, int> > primes;
vector<int> divi, pr;

inline void calc(int p = 0, int x = 1) {
    if(p == primes.size()) {
        divi.pb(x);
        return;
    }
    calc(p + 1, x);
    for(int i = 0; i < primes[p].second; ++i) {
        x *= primes[p].first;
        calc(p + 1, x);
    }
}

inline void gen_divisors(int n)
{
    primes.clear();
    divi.clear();
    while(n > 1)
    {
        int x = lp[n], st = 0;
        while(n % x == 0) n /= x, st++;
        primes.pb(x, st);
    }
    calc();
}

int sign, cur_id, s2;

inline void gen_masks(int p = 0, int x = 1, int c = 0) {
    if(p == pr.size()) {
        if(c) s2 = -1;
        else s2 = 1;
        ans[cur_id] += cnt[x] * s2 * sign;
        return ;
    }
    gen_masks(p + 1, x * pr[p], c ^ 1);
    gen_masks(p + 1, x, c);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    sieve();
    cin >> n;
    fo(i, n) {
        cin >> a[i];
    }
    cin >> q;
    fo(it, q) {
        cin >> l[it] >> r[it] >> X[it];
        e[l[it]-1].pb(-it);
        e[r[it]].pb(it);
    }
    fo(i, n) {
        gen_divisors(a[i]);
        for(int j : divi) cnt[j]++;
        for(int t = 0; t < e[i].size(); ++t) {
            int id = e[i][t], x = X[abs(id)];
            pr.clear();
            while(x > 1) {
                int y = lp[x];
                pr.pb(y);
                while(x % y == 0) x /= y;
            }
            sign = (id < 0 ? -1 : 1), cur_id = abs(id);
            gen_masks();
        }
    }
    fo(it, q) cout << ans[it] << '\n';

    return 0;
}