Здравствуйте! Идеи, как решить следующую задачу, зашли в тупик, поэтому нужна помощь:

У нас есть массив a[1...n] (n ≤ 200000, 1 ≤ a[i] ≤ 1000000) из целых чисел и есть q запросов к этому массиву (q ≤ 200000) вида: l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 1000000). Для каждого запроса мы должны ответить сколько есть различных индексов j таких что l_i ≤ j ≤ r_i и gcd(a[j], x) = 1.

Вот, что удалось осознать:

1) До 1.000.000 всего 78.498 простых чисел.

2) Каждое число во вводе не может иметь более 7 различных простых делителей, так как 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

Ограничения по времени 1.5 с, памяти 32 MB.

Задача была на полуфинале ВКОШП в Красноярском крае в сезоне 2017/2018 как задача "G. Скучные запросы". Разбор и архив жюри найти не удалось, а очень хочется. Здесь ее можно сдать, ограничения по времени немного увеличены в сравнении с оригиналом, так как сервер не самый быстрый, а система 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: решено Aeon. Memory: 21 MB, Time: 1.2 s на худшем случае.