Переберем начало подпоследовательности и будем добавлять новое число и считать НОД. Получившиеся значение положим в множество. В конце выведем размер множества. Но такое решение будет работать за $$$O(N^2 log_2~10^{18})$$$. Если добавить следующее отсечение: НОД последовательности стал равен 1, то больше добавлять новые числа нет смысла, так как НОД не изменится. Такая оптимизация позволит пройти ещё несколько тестов, но всё равно не даёт решить задачу на полный балл.
Заметим, что НОД подпоследовательности чисел не может возрастать при добавлении очередных элементов в подпоследовательность и таким образом не может принять более $$$log_2~10^{18}$$$ значений (примерно 64). Пусть $$$D_i = \{ $$$НОД$$$(a_j , a_{j+1}, \dots, a_{i-1}, a_i )~|~j \le i \}$$$ при этом размер $$$D_i$$$ не превышает $$$O(log_2~a_{i} )$$$. Тогда можно рассчитать $$$D_{i+1} = \{ $$$НОД$$$(v, a_{i+1})~|~v \in D_i \}~\cup~\{ a_{i+1} \}$$$. Все новые значения добавить в множество, в котором будем хранить все НОД. Тогда время работы алгоритма $$$O(N log_2^2~10^{18})$$$