409972: GYM103870 Q Food Poisoning

There used to exist a good story about someone getting food poisoning from eating at restaurants. It is now replaced by a cleaner statement.

You have an integer $$$N$$$ and a set of primes that initially contains the first $$$M$$$ primes. You have to handle $$$Q$$$ queries, where for each query, you make a modification to the set of primes. You either insert a prime that is not present in the set already or delete a prime that is already present in the set. After each query, you have to output the number of numbers $$$x$$$ $$$(1 \leq x \leq N)$$$ such that $$$x$$$ is divisible by at least one prime in the set. All operations will only consist of the first $$$M$$$ primes.

The first line of input contains $$$3$$$ integers $$$N$$$, $$$M$$$, $$$Q$$$ $$$(1 \leq N \leq 10^6, 1 \leq M \leq N, 1 \leq Q \leq 10^5)$$$, the number of numbers to maintain in the queries, the number of primes that are set initially, and the number of modifications initially. It is guaranteed the $$$M$$$'th prime number is not greater than $$$N$$$.

The following $$$Q$$$ lines contain one integer each, $$$x$$$, denoting the prime to be updated, meaning that you are either inserting the $$$x$$$'th prime or deleting the $$$x$$$'th prime. If the $$$x$$$'th prime is already present, you will remove it from the set. Otherwise, the $$$x$$$'th prime is not present, and you are inserting it into the set.

For testcases $$$1$$$ - $$$2$$$, $$$(1 \leq N, Q, \leq 10^3)$$$.

For testcases $$$3$$$ - $$$4$$$, each element is only queried at most once.

For testcases $$$5$$$ - $$$6$$$, $$$(1 \leq M \leq 10)$$$.

For testcases $$$7$$$ - $$$10$$$, $$$(1 \leq n \leq 10^4)$$$.

There are no additional constraints on the remaining testcases.

Output $$$Q$$$ lines, one integer each, the $$$i$$$'th line denoting the number of primes that are divisible by at least one prime in the set after the $$$i$$$'th update.

Note that the number $$$1$$$ will never be divisible by any primes in the set.

10 4 7
1
2
1
2
3
1
4

6
3
7
9
8
4
3

$$$p_1 = 2 \\ p_2 = 3 \\ p_3 = 5 \\ p_4 = 7$$$

Let $$$S$$$ denote the elements from $$$1 \cdots 10$$$ that are divisible by at least one prime in the set.

After the first query, $$$S$$$ is $$$[3, 5, 6, 7, 9, 10]$$$.

After the second query, $$$S$$$ is $$$[5, 7, 10]$$$.

After the third query, $$$S$$$ is $$$[2, 4, 5, 6, 7, 8, 10]$$$.

After the fourth query, $$$S$$$ is all the numbers from $$$1 \cdots 10$$$ aside from the number $$$1$$$.

After the fifth query, $$$S$$$ is all the numbers from $$$1 \cdots 10$$$ aside from numbers $$$1$$$ and $$$5$$$.

After the sixth query, $$$S$$$ is $$$[3, 6, 7, 9]$$$.

After the last query, $$$S$$$ is $$$[3, 6, 9]$$$.

—

Idea: Everule, 3366

Preparation: 3366

Occurrences: Advanced 10