B - Division 2

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

うさぎは, プログラミングコンテストで今 Division 2 であり, なかなか Division 1 に上がれない。

そのため, うさぎは整数を 2 で割ることに対して恨みを持っている。

ところで, 今, うさぎは, 1 から n までの数字を黒板に書き, 以下の操作を q 回しようとしている。

  • i 回目の操作のとき, 黒板に書かれている数の中で a_i で割り切れるものがあればその数を a_i1 回だけ割る。

最終的に 1 が何個残るでしょうか?


入力

入力は以下の形式で標準入力から与えられる。

n q
a_1
:
a_q
  • 1 行目には, 黒板に書く数の個数n と処理の回数qが空白区切りで与えられる。
  • 2 行目から, q 行にわたって a_i が与えられる。 a_ii 番目の処理で割る数を表す。

出力

出力は以下の形式で標準出力に従うこと。

  • 最終的に、黒板に「1」が何個書かれているか、1行で出力してください。

制約

  • 1n{10}^{13}
  • 1q24
  • 3a_i50

小課題

小課題 1 [ 25 点 ]

  • 1≦n≦10^6 を満たす。

小課題 2 [ 75 点 ]

  • 追加の制約はない。

入力例1

7 2
3
6

出力例1

2

数字は以下のように変化する。

1 2 3 4 5 6 7
3で割る 1 2 1 4 5 2 7
6で割る 1 2 1 4 5 2 7

よって、1,32つの場合最終的に1になる。

入力例2

7 2
6
3

出力例2

3

数字は以下のように変化する。

1 2 3 4 5 6 7
6で割る 1 2 3 4 5 1 7
3で割る 1 2 1 4 5 1 7

よって、1,3,63つの場合最終的に1になる。

入力例3

8 4
4
8
16
32

出力例3

2

数字は以下のように変化する。

1 2 3 4 5 6 7 8
4で割る 1 2 3 1 5 6 7 2
8で割る 1 2 3 1 5 6 7 2
16で割る 1 2 3 1 5 6 7 2
32で割る 1 2 3 1 5 6 7 2

よって、1,42つの場合最終的に1になる。

入力例4

50 4
8
6
4
3

出力例4

9

問題文担当者:square1001