Hello, codeforces! How we can solve this problem:↵
↵
We are given an array $a[1...n]$ $(n \le 200000, 1 \le a[i] \le 1000000)$ of integers and given $q$ queries $(q \le 200000)$: $l_i, r_i, x_i$ $(1 \le l_i \le r_i \le n, 1 \le x_i \le 1000000)$. For each query we need to answer how many indexes $j: l_i \le j \le 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 \times 3 \times 5 \times 7 \times 11 \times 13 \times 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](https://ideone.com/RW7RFT) by [user:AeonHQ,2018-06-09]. Memory: 21 MB, Time: 1.2 s on worst case.↵
↵
We are given an array $a[1...n]$ $(n \le 200000, 1 \le a[i] \le 1000000)$ of integers and given $q$ queries $(q \le 200000)$: $l_i, r_i, x_i$ $(1 \le l_i \le r_i \le n, 1 \le x_i \le 1000000)$. For each query we need to answer how many indexes $j: l_i \le j \le 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 \times 3 \times 5 \times 7 \times 11 \times 13 \times 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](https://ideone.com/RW7RFT) by [user:AeonHQ,2018-06-09]. Memory: 21 MB, Time: 1.2 s on worst case.↵
