Hello, codeforces! How we can solve this problem:

We are given an array a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) of integers and given q queries (q ≤ 200000): l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 1000000). For each query we need to answer how many indexes j: l_i ≤ j ≤ r_i and gcd(a[j], x) = 1.

Here's what I got:

1) before 1.000.000 only 78.498 primes

2) each number from input have no more than 7 prime divisors, because 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510.510

3) count(l_i, r_i, x_i) = count(1, r_i, x_i) - count(1, l_i - 1, x_i), l_i > 1

Time Limit is 1.5 s, Memory Limit is 64 MB.

Example:

6
1 2 3 4 5 6
4
1 6 1 --> 6
1 6 2 --> 3
2 4 6 --> 0
3 6 10 --> 1

UPD: solved by Aeon. Memory: 21 MB, Time: 1.2 s on worst case.