Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2166. Выборы
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 25/07/2014 | Лето 2014 - 19 (C) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Источник: neerc.ifmo.ru/school
