Количество элементов в заданном массиве, кратное всем элементам в их префиксе

Дан массив arr[] , содержащий N положительных целых чисел, задача состоит в том, чтобы найти общее количество элементов в массиве, которые делятся на все элементы, находящиеся перед ними.

Примеры:

Input: arr[] = {10, 6, 60, 120, 30, 360}
Output: 3
Explanation: 60, 120 and 360 are the required elements.

Input: arr[] = {2, 6, 5, 60}
Output: 2
Explanation: 6 and 60 are the elements.

Подход: Как известно, любое число X делится на {X ₁ , X ₂ , X ₃ , X ₄ , . . ., X _n } , если X делится на НОК {X ₁ , X ₂ , X ₃ , X ₄ , …, X _n ). И LCM любого числа A , B равно [(A*B)/gcd(A, B)] . Теперь, чтобы решить эту проблему, выполните следующие действия:

1. Создайте переменную ans , в которой хранится окончательный ответ, и инициализируйте ее значением 0.
2. Создайте еще одну переменную lcm , которая хранит LCM до i ^-го элемента при переборе массива. Инициализируйте lcm с помощью arr[0] .
3. Перебираем массив от i = 1 до i = N и на каждой итерации проверяем, делится ли arr[i] на lcm. Если да, увеличьте ans на 1. Также обновите lcm с помощью lcm до i ^-го элемента.
4. Выведите ответ как окончательный ответ на эту задачу.

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

Временная сложность: O(N * logD), где D — максимальный элемент массива
Вспомогательное пространство: НА)