M. Хотя бы на одно делится

Посчитайте, сколько целых чисел от 1 до $N$ делятся хотя бы на одно из данных $k$ чисел.

В классе числа были произвольными, и здесь тоже: считать надо через наименьшее общее кратное, а не через произведение. Разница видна на наборе $4$ и $6$: их произведение 24, а общее кратное 12.

И одна ловушка: наименьшее общее кратное пятнадцати чисел до миллиона легко превосходит любой тип. Как только оно стало больше $N$, дальше считать незачем.

Первая строка содержит числа $N$ ($1 \le N \le 10^{12}$) и $k$ ($1 \le k \le 15$).

Вторая строка содержит $k$ различных чисел $a_i$ ($2 \le a_i \le 10^6$).

Одно число — количество чисел от 1 до $N$, делящихся хотя бы на одно из данных.