← 返回题目列表

AtCoder · maximum_cup_2023_c

C. 黒板

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

配点 : 100 点

問題文

黑板上 N 以下正整数是 1 一一写着。另外,M 正整数 给出了 x_1,\ldots,x_M 。在这里,i \neq j 如果 x_i 和 x_j 保证是不相交的。  

您可以执行以下操作 您可以根据需要多次执行此操作 0 。

  • 1 以上 M 的整数 声明 i 有一定的 x_i 的倍数 选择 y 。黑板上 如果写入 y ,则 选择 1 并 重写为\frac{y}{x_i} 。

运算结束后,求黑板上写的整数之和最小。

制約

  • 1 \leq N \leq 2 \times 10^9
  • 1 \leq M \leq 300
  • 1 \leq x_i \leq 2 \times 10^9
  • i \neq j 如果 x_i 和 x_j 不相交
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
x_1 \ldots x_M

出力

输出答案。


入力例 1

10 2
2 3

出力例 1

24

写入的整数为 如果从 (1,2,3,4,5,6,7,8,9,10) 状态执行以下操作,则写入的整数之和将为 24 。这是最小值。 操作方式为

  • i=1, y=2 。写入的整数是 (1,1,3,4,5,6,7,8,9,10) 变为。
  • i=2, y=9 。写入的整数是 (1,1,3,4,5,6,7,8,3,10) 变为。
  • i=2, y=3 。写入的整数是 (1,1,1,4,5,6,7,8,3,10) 变为。
  • i=1, y=8 。写入的整数是 (1,1,1,4,5,6,7,4,3,10) 变为。
  • i=1, y=10 。写入的整数是 (1,1,1,4,5,6,7,4,3,5) 变为。
  • i=2, y=3 。写入的整数是 (1,1,1,4,5,6,7,4,1,5) 变为。
  • i=2, y=99 。写入的整数是 (1,1,1,4,5,6,7,4,1,5) 变为。
  • i=1, y=4 。写入的整数是 (1,1,1,2,5,6,7,4,1,5) 变为。
  • i=1, y=2 。写入的整数是 (1,1,1,1,5,6,7,4,1,5) 变为。
  • i=1, y=6 。写入的整数是 (1,1,1,1,5,3,7,4,1,5) 变为。
  • i=2, y=3 。写入的整数是 (1,1,1,1,5,1,7,4,1,5) 变为。
  • i=1, y=4 。写入的整数是 (1,1,1,1,5,1,7,2,1,5) 变为。
  • i=1, y=2 。写入的整数是 (1,1,1,1,5,1,7,1,1,5) 变为。

入力例 2

2000000000 3
20 23 7

出力例 2

1597222223653885214