問題一覧 > 通常問題

No.2620 Sieve of Coins

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : startcpp / テスター : 👑 Nachia
2 ProblemId : 10452 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-01-27 14:39:47

問題文

机の上に LL 枚のコインが置かれています。
左から ii ( 1≤i≤L1 \le i \le L ) 枚目のコインをコイン ii と呼ぶことにすると、
コインA1,⋯ ,ANA_1, \cdots, A_N は表向き、それ以外のコインは裏向きになっています。
この状態から開始し、i=1,⋯ ,Li = 1, \cdots, L の順で以下の操作を行います。

  • コイン ii が裏向きなら何もしない。
  • コイン ii が表向きなら、各整数 jj ( 2≤j≤⌊Li⌋2 \le j \le \lfloor \frac{L}{i} \rfloor ) について、コイン i×ji \times j の表裏を反転する。
最後の操作が終了したとき、表向きになっているコインは何枚あるでしょうか？

入力

LL NN
A1A_1 ⋯\cdots ANA_N

全てのテストケースは以下の制約を満たす。

  • 入力は全て整数
  • 1≤L≤10121 \le L \le 10^{12}
  • 1≤N≤5341 \le N \le 534
  • 1≤A1<⋯<AN≤L1 \le A_1 \lt \cdots \lt A_N \le L
  • AiA_i (1≤i≤N1 \le i \le N) は 55 以上の素因数を持たない
テストケースは sample_01.txt～sample_05.txt, subtask1_*.txt, subtask2_*.txt, subtask3_*.txt, subtask4_*.txt の順に配置する。
各テストケース名において、追加で以下の制約を満たす。
  • sample_01.txt～sample_05.txtは、サンプル1～サンプル5に対応する
  • subtask1_*.txt（1111 ケース）では、L≤105L \le 10^{5} を満たす
  • subtask2_*.txt（1212 ケース）では、N=1N = 1 を満たす
  • subtask3_*.txt（1717 ケース）では、N≤20N \le 20 を満たす
  • subtask4_*.txt（1313 ケース）では、追加の制約はない
実行時間超過 (TLE) をした場合、その先のテストケースは採点されません。
また、コンテスト本番ではACを取るまでテストケース名が見えないので、subtaskを試す場合は制約を満たさないケースをassert文などでRuntime Errorにすることを推奨します。

出力

答えとなる整数を 11 行で出力してください。最後に改行してください。

サンプル

サンプル1
入力
8 1
1
出力
6

コインの表裏は次のようになります。
44 回目の操作ではコイン 44 が裏向きなので、コイン 88 の向きはそのままになります。
55 回目以降の操作ではコインの反転が起こりません。
したがって、最終的にはコイン 1,2,3,5,6,71, 2, 3, 5, 6, 7 の 66 枚が表を向いています。

操作回数 コインの表裏
00 表, 裏, 裏, 裏, 裏, 裏, 裏, 裏
11 表, 表, 表, 表, 表, 表, 表, 表
22 表, 表, 表, 裏, 表, 裏, 表, 裏
33 表, 表, 表, 裏, 表, 表, 表, 裏
44 表, 表, 表, 裏, 表, 表, 表, 裏

サンプル2
入力
8 3
1 2 3
出力
5

コインの表裏は次のようになります。
11 回目の操作によってコイン 2,32, 3 が裏を向きます。
よって、2,32, 3 回目の操作では反転が起こりません。
44 回目の操作では コイン 44 が表向きです。
そのため、コイン88 の向きが表から裏になります。
55 回目以降は反転が起こりません。
よって、最終的にはコイン 1,4,5,6,71, 4, 5, 6, 7 の 55 枚が表向きになります。

操作回数 コインの表裏
00 表, 表, 表, 裏, 裏, 裏, 裏, 裏
11 表, 裏, 裏, 表, 表, 表, 表, 表
22 表, 裏, 裏, 表, 表, 表, 表, 表
33 表, 裏, 裏, 表, 表, 表, 表, 表
44 表, 裏, 裏, 表, 表, 表, 表, 裏

サンプル3
入力
100000 8
1 2 3 4 6 8 9 12
出力
37999

このケースは、subtask1_*.txt、subtask3_*.txt、subtask4_*.txt の制約を満たします。

サンプル4
入力
1000000000000 1
1
出力
607927102274

このケースは、subtask2_*.txt、subtask3_*.txt、subtask4_*.txt の制約を満たします。

サンプル5
入力
1000000000000 8
1 2 3 4 6 8 9 12
出力
379954438788

このケースは、subtask3_*.txt、subtask4_*.txt の制約を満たします。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。