Хорошее подмножество

В данной задаче ограничения на числа $$$a_i \leq 10^{18}$$$.

В данных ограничениях задачу можно решать следующим образом:

Проверим как НОД все простые $$$\leq 10^6$$$. Для этого для каждого простого в этом интервале проверим, сколько чисел на него делится, разделим эти числа на максимальную степень этого простого, на которую он делится. И прорелаксируем ответ количеством.

Теперь все числа состоят не больше чем из двух различных простых множителей.

Далее утверждается, что как возможный НОД в ответе достаточно рассмотреть только попарные НОДы чисел.

Таким образом можно выделить все различные НОДы пар, и проверить количество чисел, которые на них делятся, прорелаксировав этими величинами ответ.

Авторское решение работает при больших ограничениях на числа, к примеру $$$a_i \leq 10^{36}$$$.

Для того чтобы решить задачу в таких ограничениях давайте поддерживать неразделимые «группы», такое множество попарно взаимно простых чисел, что каждое данное число можно представить в виде произведения чисел из этого множества.

Очевидно, в этом множестве не больше чем $$$C \cdot n$$$ чисел, где $$$C$$$ — максимальное количество разных простых, которые есть в числах. В ограничениях $$$a_i \leq 10^{18}$$$, $$$C=15$$$, очевидно, при $$$a_i \leq 10^{36}$$$, $$$C \leq 30$$$, но на самом деле меньше

Как найти эти группы? Давайте добавлять числа по одному и поддерживать это разбиение для текущего префикса чисел. При добавлении нового числа $$$x$$$, если найдется число $$$y$$$ из множества, которое имеет НОД $$$g$$$ больший, чем один, с данным числом, можно заменить это число $$$y$$$ из группы на $$$g$$$, и попытаться добавить в группу числа $$$\frac{x}{g}$$$ и $$$\frac{y}{g}$$$. Если же в какой-то момент мы пытаемся добавить в группу число $$$1$$$, следует выйти. Авторское решение производит добавления в группу с помощью рекурсивного алгоритма.

Таким образом за $$$O(C \cdot n^2)$$$ можно найти эти неразделимые группы, а затем для каждой группы посчитать количество чисел, которые делятся на это значение, и прорелаксировать этим ответом.