Количество различных взаимно простых пар, произведение которых делит все элементы в индексе [L, R] для Q запросов

Дан массив arr[] из N целых чисел и Q запросов вида (l, r) . Задача состоит в том, чтобы найти количество различных пар взаимно простых целых чисел для каждого запроса, таких что все целые числа в диапазоне индексов [l, r] делятся на произведение взаимно простых чисел.

Примеры:

Input: arr[] = {1, 2, 2, 4, 5}, queries[] = {{2, 3}, {2, 4}, {3, 4}, {4, 4}, {4, 5}}
Output: 3 3 3 5 1
Explanation: For 1st query [2, 3], the subarray is {2, 2}. 
The pairs of coprimes that divide all the integers in the subarray are {1, 1}, {1, 2} and {2, 1}. 
For 2nd query [2, 4], the subarray is {2, 2, 4}. 
The pairs of coprimes that divide all the integers are {1, 1}, {1, 2} and {2, 1}. 
Similarly, proceed for the further queries.

Input: arr[] = {20, 10, 15}, queries[] = {{2, 3}, {1, 3}, {1, 2}}
Output: 3 3 9 

Подход: Данную задачу можно оптимально решить с помощью разреженной таблицы. Подход основан на том, что только простые множители НОД подмассива могут делить все его элементы. Следовательно, простые множители НОД вносят вклад в подсчет пар. НОД диапазонов можно оптимально рассчитать с помощью разреженной таблицы. Ниже приведены шаги, которые необходимо выполнить:

• Создайте разреженную таблицу, чтобы найти элементы GCD в диапазоне [L, R] в оптимальное время по нескольким запросам.
• Переберите массив запросов и для каждого запроса выполните следующее:
  • Найдите НОД элементов в диапазоне [L, R] для текущего запроса.
  • Теперь задача сводится к нахождению количества взаимно простых пар в диапазоне [1, GCD] , произведение которых равно GCD , что можно сделать с помощью обсуждаемого здесь алгоритма.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(Q * sqrt(M) * log M), где M — максимальное целое число в данном массиве.
Вспомогательное пространство: O(M*log M)