問題一覧 > 通常問題

No.1946 ロッカーの問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : H20H20 / テスター : platinumplatinum 蜜蜂蜜蜂
3 ProblemId : 7890 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-05 18:06:54

問題文

学校には $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もしくは右上の雲マークをクリックしてアカウントを作成してください。