↵
We are given an array
↵
У нас есть массив $a[1...n]$ $(n \le 200000, 1 \le a[i] \le 1000000)$
↵
↵
1)
↵
2) each number from input have no more than $7$ prime divisors, because
↵
2) Каждое число во вводе не может иметь более $7$ различных простых делителей, так как $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$↵
↵
↵
Example
↵
Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 2017/2018 как задача "G. Скучные запросы". Разбор и архив жюри найти не удалось, а очень хочется. [Здесь](https://acmp.ru/asp/do/index.asp?main=task&id_course=3&id_section=25&id_topic=191&id_problem=1262) ее можно сдать, ограничения по времени немного увеличены в сравнении с оригиналом, так как сервер не самый быстрый, а система 32-битная.↵
↵
Пример:↵
↵
~~~~~↵
6↵
1 2 3 4 5 6↵
4↵
1 6 1 --> 6↵
1 6 2 --> 3↵
2 4 6 --> 0↵
3 6 10 --> 1↵
~~~~~↵
↵
