No.2620 Sieve of Coins
タグ : / 解いたユーザー数 13
作問者 :
startcpp
/ テスター :
👑 
Nachia
問題文
机の上に $L$ 枚のコインが置かれています。
左から $i$ ( $1 \le i \le L$ ) 枚目のコインをコイン $i$ と呼ぶことにすると、
コイン$A_1, \cdots, A_N$ は表向き、それ以外のコインは裏向きになっています。
この状態から開始し、$i = 1, \cdots, L$ の順で以下の操作を行います。
- コイン $i$ が裏向きなら何もしない。
- コイン $i$ が表向きなら、各整数 $j$ ( $2 \le j \le \lfloor \frac{L}{i} \rfloor$ ) について、コイン $i \times j$ の表裏を反転する。
入力
$L$ $N$ $A_1$ $\cdots$ $A_N$
全てのテストケースは以下の制約を満たす。
- 入力は全て整数
- $1 \le L \le 10^{12}$
- $1 \le N \le 534$
- $1 \le A_1 \lt \cdots \lt A_N \le L$
- $A_i$ ($1 \le i \le N$) は $5$ 以上の素因数を持たない
sample_01.txt～sample_05.txt, subtask1_*.txt, subtask2_*.txt, subtask3_*.txt, subtask4_*.txt の順に配置する。各テストケース名において、追加で以下の制約を満たす。
sample_01.txt～sample_05.txtは、サンプル1～サンプル5に対応するsubtask1_*.txt（$11$ ケース）では、$L \le 10^{5}$ を満たすsubtask2_*.txt（$12$ ケース）では、$N = 1$ を満たすsubtask3_*.txt（$17$ ケース）では、$N \le 20$ を満たすsubtask4_*.txt（$13$ ケース）では、追加の制約はない
また、コンテスト本番ではACを取るまでテストケース名が見えないので、subtaskを試す場合は制約を満たさないケースをassert文などで
Runtime Errorにすることを推奨します。出力
答えとなる整数を $1$ 行で出力してください。最後に改行してください。
サンプル
サンプル1
入力
8 1 1
出力
6
コインの表裏は次のようになります。
$4$ 回目の操作ではコイン $4$ が裏向きなので、コイン $8$ の向きはそのままになります。
$5$ 回目以降の操作ではコインの反転が起こりません。
したがって、最終的にはコイン $1, 2, 3, 5, 6, 7$ の $6$ 枚が表を向いています。
| 操作回数 | コインの表裏 |
|---|---|
| $0$ | 表, 裏, 裏, 裏, 裏, 裏, 裏, 裏 |
| $1$ | 表, 表, 表, 表, 表, 表, 表, 表 |
| $2$ | 表, 表, 表, 裏, 表, 裏, 表, 裏 |
| $3$ | 表, 表, 表, 裏, 表, 表, 表, 裏 |
| $4$ | 表, 表, 表, 裏, 表, 表, 表, 裏 |
サンプル2
入力
8 3 1 2 3
出力
5
コインの表裏は次のようになります。
$1$ 回目の操作によってコイン $2, 3$ が裏を向きます。
よって、$2, 3$ 回目の操作では反転が起こりません。
$4$ 回目の操作では コイン $4$ が表向きです。
そのため、コイン$8$ の向きが表から裏になります。
$5$ 回目以降は反転が起こりません。
よって、最終的にはコイン $1, 4, 5, 6, 7$ の $5$ 枚が表向きになります。
| 操作回数 | コインの表裏 |
|---|---|
| $0$ | 表, 表, 表, 裏, 裏, 裏, 裏, 裏 |
| $1$ | 表, 裏, 裏, 表, 表, 表, 表, 表 |
| $2$ | 表, 裏, 裏, 表, 表, 表, 表, 表 |
| $3$ | 表, 裏, 裏, 表, 表, 表, 表, 表 |
| $4$ | 表, 裏, 裏, 表, 表, 表, 表, 裏 |
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。