問題
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