| Codeforces Beta Round 76 (Div. 1 Only) |
|---|
| Закончено |
Игорь К. очень любит многопользовательскую ролевую игру WineAge II. Кто знает, возможно, именно в ней причина его не слишком успешной учебы в университете. Как и любой играющий в нее человек, он заинтересован в том, чтобы экипировка и оружие его персонажа были как можно лучше.
Однажды, в очередной раз читая форум этой игры, он наткнулся на очень интересный факт. Оказывается, каждое оружие в игре характеризуется k различными числами: a1, ..., ak. Они называются показателями удара и по задумке разработчиков игры являются попарно взаимно простыми.
Урон, наносящийся при ударе, зависит не только от характеристик оружия, но и от показателя силы персонажа. Так, если сила персонажа равна n, то наносимый урон будет вычисляться как количество чисел на отрезке 
, которые не делятся ни на один из показателей удара ai.
Недавно, выполнив очередной квест, Игорь К. нашел новый меч Лостборн. Он хочет знать, сколько урона он будет наносить своим противникам, используя его.
В первой строке записаны два целых числа: n и k (1 ≤ n ≤ 1013, 1 ≤ k ≤ 100) — показатель силы персонажа Игоря К. и количество показателей удара.
В следующей строке через пробел перечислены k целых чисел ai (1 ≤ ai ≤ 1000) — показатели удара меча Лостборн. k заданных чисел являются попарно взаимно простыми.
Выведите единственное число — урон, который будет наносить персонаж Игоря К. при применении своего нового оружия.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
20 3
2 3 5
6
50 2
15 8
41
