005 - Expansion FizzBuzz

問題

FizzBuzzという問題がある。今回はこの問題を拡張した問題を出題する。

長さ$M$の数列{$A_1, A_2, ..., A_M$}と友人Fがある。

任意の自然数$X$に対し、友人Fは$X$が$A_1$の倍数であるとき"foo"、$A_2$の倍数であるとき"bar"といった決められた文字列をいう。$A_i$の倍数である$∧A_j$の倍数であるときはそれぞれに対応する文字列を連結し発言する($A_1$の倍数かつ$A_2$の倍数であるときは"foobar")。

3つ以上の値の倍数であるときも、同様に連結する。

$M$個すべての整数の倍数でないときは、$X$自身を言う。

$X$に対する友人Fの返答を$f(X)$とする。

自然数$N$が与えられる。$1$以上$N$以下の整数$i$のうち、$f(i)$が$i$である個数を出力せよ。

入力

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

$N$ $M$
$A_1$ $A_2$ ... $A_M$

1行目に整数$N$、$M$が与えられる。

2行目に整数$A_1, A_2, ... , A_M$が与えられる。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N \leq 10^{8}$
• $1 \leq M \leq 20$
• $1 \leq A_i \leq 10^{9} (1 \leq i \leq M)$
• $A_i \leq A_{i+1} (1 \leq i \lt M)$

入出力例

入力例1

15 2
3 5

出力例1

8

本来のFizzBuzzに近い形である。

出力は1, 2, foo, 4, bar, foo, 7, 8, foo, bar, 11, foo, 13, 14, foobar となる。ここで$f(x) = x$となるのは8つある。

入力例2

100 5
2 3 5 7 11

出力例2

21

100までの素数の数 - 4

入力例3

10000000 10
123 456 7890 1234 5678 9012 34567 89012 345678 901234

出力例2

9884855

出力は高々$N$なので剰余を取る必要はない。

余談

1.foo 2.bar 3.baz 4.qux 5.quux 6.corge 7.grault 8.garply 9.waldo 10.fred 11.plugh 12.xyzzy 13.thud