No.1946 ロッカーの問題
タグ : / 解いたユーザー数 149
作問者 :
H20
/ テスター :
蜜蜂
platinum
問題文
学校には $N$ 人の生徒がいて、$1$ 番から $N$ 番までの番号が付けられた $N$ 個のロッカーがあります。
ロッカーは全て閉じた状態です。
$N$ 人の生徒に対して一人ずつ順番に以下の規則に従って、ロッカーの開け閉めを行うように指示しました。
規則：$i$ 人目の生徒は、$i$ の約数である番号がついたロッカーを開いていれば閉め、閉じていれば開く。
しかしながら、幾人かの生徒がサボり、一切操作を行っていない可能性があるとの報告がありました。
$N$ 人の操作が完了した状態で開いているロッカーの個数が $M$個 、開いたロッカーの番号が $A_1, A_2, \ldots, A_M$ でした。
開いているロッカーの番号からサボった生徒の人数が一意に定まります。サボった生徒の人数を出力してください。
入力
$N\ M$ $A_1$ $A_2$ $\ldots$ $A_M$
制約
- $ 1 \le N \le 2\times10^{5}$
- $ 0 \le M \le N$
- $ 1 \le A_i \le N$
- $A_1 \lt A_2 \lt \ldots \lt A_M$
- 入力は全て整数
出力
サボった生徒の人数を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 3 1 2 5
出力
3
$3$ 人目と$4$ 人目と$6$ 人目の生徒がサボりました。開いているロッカーは以下のように変化します。
$1$ 人目操作後に開いているロッカー: $1$
$2$ 人目操作後に開いているロッカー: $2$
$5$ 人目操作後に開いているロッカー: $1,2,5$
サンプル2
入力
10 5 2 4 5 8 9
出力
6
$1$ 人目, $2$ 人目, $4$ 人目, $6$ 人目, $7$ 人目, $10$ 人目がサボったようです。
サンプル3
入力
200000 0
出力
200000
全員でサボタージュしたようです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。