Здравствуйте! Идеи, как решить следующую задачу, зашли в тупик, поэтому нужна помощь:↵
↵
У нас есть массив $a[1...n]$ $(n \le 200000, 1 \le a[i] \le 1000000)$ из целых чисел и есть $q$ запросов к этому массиву $(q \le 200000)$ вида: $l_i, r_i, x_i$ $(1 \le l_i \le r_i \le n, 1 \le x_i \le 1000000)$. Для каждого запроса мы должны ответить сколько есть различных индексов $j$ таких что $l_i \le j \le r_i$ и $gcd(a[j], x) = 1$.↵
↵
Вот, что удалось осознать: ↵
↵
1) До $1.000.000$ всего $78.498$ простых чисел.↵
↵
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$↵
↵
Ограничения по времени 1.5 с, памяти 32 MB.↵
↵
Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 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↵
~~~~~↵
↵
UPD: [решено](https://ideone.com/RW7RFT) [user:AeonHQ,2018-06-09]. Memory: 21 MB, Time: 1.2 s на худшем случае.
↵
У нас есть массив $a[1...n]$ $(n \le 200000, 1 \le a[i] \le 1000000)$ из целых чисел и есть $q$ запросов к этому массиву $(q \le 200000)$ вида: $l_i, r_i, x_i$ $(1 \le l_i \le r_i \le n, 1 \le x_i \le 1000000)$. Для каждого запроса мы должны ответить сколько есть различных индексов $j$ таких что $l_i \le j \le r_i$ и $gcd(a[j], x) = 1$.↵
↵
Вот, что удалось осознать: ↵
↵
1) До $1.000.000$ всего $78.498$ простых чисел.↵
↵
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$↵
↵
Ограничения по времени 1.5 с, памяти 32 MB.↵
↵
Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 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↵
~~~~~↵
↵
UPD: [решено](https://ideone.com/RW7RFT) [user:AeonHQ,2018-06-09]. Memory: 21 MB, Time: 1.2 s на худшем случае.
