← 返回题目列表

Codeforces · 93/E

E. 失落的诞生

中文机器翻译题面 查看原题

Igor K. 非常喜欢多人角色扮演游戏 WineAge II。谁知道,也许这就是他在大学表现不佳的原因。作为任何玩这款游戏的人,他都有兴趣为他的英雄配备尽可能好的武器和装备。

有一天,他再次浏览游戏论坛时,发现了一个很有趣的事实。事实证明,游戏中的每种武器都有 k 个不同的数字:a1,...,ak。它们被称为命中指标,根据游戏开发者的计划,它们是成对互质的。

击中时造成的伤害不仅取决于武器的特性,还取决于英雄的力量参数。因此,如果英雄的力量等于n,那么所造成的伤害将被计算为线段$${\bigl [}1,n{\bigr ]}$$上的数字数量,这些数字不能被任何命中指标ai整除。

最近,在完成另一个任务后,Igor K. 发现了一把新的 Lostborn 剑。他想知道如果他使用它会给敌人造成多少伤害。

输入

第一行包含两个整数:n 和 k (1 ≤ n ≤ 1013, 1 ≤ k ≤ 100)。它们是伊戈尔K英雄强度的指标和命中指标的数量。

下一行包含用空格分隔的 k 个整数 ai (1 ≤ ai ≤ 1000)。它们是失落之剑的命中指示器。给定的 k 个数字是成对互质的。

输出

打印单个数字 - Igor K. 的英雄使用新武器时将造成的伤害。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

20 3
2 3 5

输出 #1

6

输入 #2

50 2
15 8

输出 #2

41