問題一覧 > 通常問題

No.2620 Sieve of Coins

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 14
作問者 : startcpp / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 10452 / 自分の提出
問題文最終更新日: 2024-01-27 14:39:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 416 (順位表) の他の問題:

Problem Statement

There are $L$ coins on a desk.
Let coin $i$ ( $1 \le i \le L$ ) denote the $i$-th coin from the left.
Coins $A_1, \cdots, A_N$ are face up, and all other coins are face down.
Starting from this state, perform the following operation for $i = 1, \cdots, L$ in this order.

  • If coin $i$ is face down, do nothing.
  • If coin $i$ is face up, then for each integer $j$ ( $2 \le j \le \lfloor \frac{L}{i} \rfloor$ ), flip coin $i \times j$.
How many coins are face up when the last operation has finished?

Input

$L$ $N$
$A_1$ $\cdots$ $A_N$

All test cases satisfy the following constraints.

  • All input values are integers
  • $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$) has no prime factor greater than or equal to $5$
The test cases are arranged in the order sample_01.txt～sample_05.txt, subtask1_*.txt, subtask2_*.txt, subtask3_*.txt, subtask4_*.txt.
Depending on the test case name, the following additional constraints are satisfied.
  • sample_01.txt～sample_05.txt correspond to Sample 1 through Sample 5
  • subtask1_*.txt ($11$ cases) satisfy $L \le 10^{5}$
  • subtask2_*.txt ($12$ cases) satisfy $N = 1$
  • subtask3_*.txt ($17$ cases) satisfy $N \le 20$
  • subtask4_*.txt ($13$ cases) have no additional constraints
If you get Time Limit Exceeded (TLE), the subsequent test cases will not be judged.
Also, since test case names are not visible during the contest until you get AC, if you want to try a subtask, it is recommended to make cases that do not satisfy its constraints result in Runtime Error, using an assert statement or similar.

Output

Print the integer that is the answer on $1$ line. End the output with a newline.

Sample

Sample 1
Input
8 1
1
Output
6

The states of the coins change as follows.
In operation $4$, coin $4$ is face down, so coin $8$ stays as it is.
In operation $5$ and later, no coins are flipped.
Therefore, in the end, the $6$ coins $1, 2, 3, 5, 6, 7$ are face up.

Number of operations States of the coins
$0$ Up, Down, Down, Down, Down, Down, Down, Down
$1$ Up, Up, Up, Up, Up, Up, Up, Up
$2$ Up, Up, Up, Down, Up, Down, Up, Down
$3$ Up, Up, Up, Down, Up, Up, Up, Down
$4$ Up, Up, Up, Down, Up, Up, Up, Down

Sample 2
Input
8 3
1 2 3
Output
5

The states of the coins change as follows.
Operation $1$ turns coins $2, 3$ face down.
Thus, no flips occur in operations $2, 3$.
In operation $4$, coin $4$ is face up.
Therefore, coin $8$ changes from face up to face down.
In operation $5$ and later, no flips occur.
Thus, in the end, the $5$ coins $1, 4, 5, 6, 7$ are face up.

Number of operations States of the coins
$0$ Up, Up, Up, Down, Down, Down, Down, Down
$1$ Up, Down, Down, Up, Up, Up, Up, Up
$2$ Up, Down, Down, Up, Up, Up, Up, Up
$3$ Up, Down, Down, Up, Up, Up, Up, Up
$4$ Up, Down, Down, Up, Up, Up, Up, Down

Sample 3
Input
100000 8
1 2 3 4 6 8 9 12
Output
37999

This case satisfies the constraints of subtask1_*.txt, subtask3_*.txt, and subtask4_*.txt.

Sample 4
Input
1000000000000 1
1
Output
607927102274

This case satisfies the constraints of subtask2_*.txt, subtask3_*.txt, and subtask4_*.txt.

Sample 5
Input
1000000000000 8
1 2 3 4 6 8 9 12
Output
379954438788

This case satisfies the constraints of subtask3_*.txt and subtask4_*.txt.

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