printРабочее место участника

printЗадачи

2166. Выборы

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В стране Виртландии раз в пять лет проходят выборы президента. И каждый раз после завершения голосования появляется необходимость подсчитать результаты. Рассмотрим процесс обработки бюллетеней в Виртландии.
Всего в Виртландии голосуют `n` человек, соответственно необходимо обработать `n` бюллетеней, которые пронумерованы от `1` до `n`. Обработка длится `k` дней. Каждый день члены избирательной комиссии выбирают какое-то натуральное число, после чего обрабатывают все еще не обработанные бюллетени с номерами, которые делятся нацело на выбранное число. Так, в день с номером `i` обрабатываются все бюллетени, номера которых нацело делятся на `a_i`. После завершения процесса выяснилось, что подсчитаны были не все голоса. И теперь Ваша задача – выяснить, сколько бюллетеней осталось необработанными.
В первой строке входного файла даны два целых числа `n` и `k` (`1\ ≤\ n\ ≤\ 300\ 000`, `1\ ≤\ k\ ≤\ 100\ 000`) – количество голосующих граждан и количество дней для подсчета голосов, соответственно. Во второй строке даны `k` разделенных пробелами целых чисел `a_i` (`2\ ≤\ a_i\ ≤\ n`) – числа, которые выбирались избирательной комиссией в каждый из дней.
В выходной файл выведите единственное целое число – ответ на задачу.

Пример ввода

8 2
2 3

Пример вывода

3
В примере необработанными остались бюллетени номер 1, 5 и 7.
Источник: neerc.ifmo.ru/school
loading