1497.cpp

#include <stdio.h>
#include <vector>
#include <algorithm>

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 == (int)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 == (int)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);
}

// Fastest INPUT/OUTPUT:
char getChar();
int getInt();
void putChar(char);
void putInt(int);

int main() {
    sieve();
    n = getInt();

    fo(i, n) {
        a[i] = getInt();
    }
    q = getInt();
    fo(it, q) {
        l[it] = getInt();
        r[it] = getInt();
        X[it] = getInt();
        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 < (int)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) {
        putInt(ans[it]);
        putChar('\n');
    }
    putChar(-1);

    return 0;
}

char getChar() {
    static char buf[1<<20];
    static int pos = 0;
    static int size = 0;
    if (size == pos) {
        size = fread(buf, 1, 1<<20, stdin);
        pos = 0;
    }
    if (size == pos) {
        return EOF;
    }
    return buf[pos++];
}

void putChar(char c) {
    static char buf[1<<20];
    static int size = 0;
    if (size == 1<<20 || c == -1) {
        fwrite(buf, 1, size, stdout);
        size = 0;
    }
    if (c != -1) {
        buf[size++] = c;
    }
}

int getInt() {
    char c = '?';
    while (!(c == '-' || ('0' <= c && c <= '9'))) c = getChar();
    bool positive = true;
    if (c == '-') {
        positive = false;
        c = getChar();
    }
    int answ = 0;
    while ('0' <= c && c <= '9') {
        (answ *= 10) += (c - '0');
        c = getChar();
    }
    return positive ? answ : -answ;
}

void putInt(int number) {
    if (number < 0) {
        putChar('-');
        number = -number;
    }

    char buf[14]; int pos = 0;
    do {
        buf[pos++] = number % 10 + '0';
        number /= 10;
    } while (number > 0);

    while (pos--) {
        putChar(buf[pos]);
    }
}