Removing Smallest Multiples
Contest: Codeforces Round 822 (Div. 2)
Difficulty rating: 1200
Tags: greedy, math

You are given a set $$$S$$$, which contains the first $$$n$$$ positive integers: $$$1, 2, \ldots, n$$$.

You can perform the following operation on $$$S$$$ any number of times (possibly zero):

- Choose a positive integer $$$k$$$ where $$$1 \le k \le n$$$, such that there exists a multiple of $$$k$$$ in $$$S$$$. Then, delete the smallest multiple of $$$k$$$ from $$$S$$$. This operation requires a cost of $$$k$$$.

You are given a set $$$T$$$, which is a subset of $$$S$$$. Find the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$. We can show that such a transformation is always possible.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases. The description of the test cases follows.

The first line contains a single positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line of each test case contains a binary string of length $$$n$$$, describing the set $$$T$$$. The $$$i$$$-th character of the string is '1' if and only if $$$i$$$ is an element of $$$T$$$, and '0' otherwise.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output one non-negative integer — the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we shall not perform any operations as $$$S$$$ is already equal to $$$T$$$, which is the set $$$\{1, 2, 3, 4, 5, 6\}$$$.

In the second test case, initially, $$$S = \{1, 2, 3, 4, 5, 6, 7\}$$$, and $$$T = \{1, 2, 4, 7\}$$$. We shall perform the following operations:

1. Choose $$$k=3$$$, then delete $$$3$$$ from $$$S$$$.
2. Choose $$$k=3$$$, then delete $$$6$$$ from $$$S$$$.
3. Choose $$$k=5$$$, then delete $$$5$$$ from $$$S$$$.

The total cost is $$$3+3+5 = 11$$$. It can be shown that this is the smallest cost possible.

In the third test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{\}$$$ (empty set). We shall perform $$$4$$$ operations of $$$k=1$$$ to delete $$$1$$$, $$$2$$$, $$$3$$$, and $$$4$$$.

In the fourth test case, initially, $$$S = \{1, 2, 3, 4\}$$$ and $$$T = \{3\}$$$. We shall perform two operations with $$$k=1$$$ to delete $$$1$$$ and $$$2$$$, then perform one operation with $$$k=2$$$ to delete $$$4$$$.

Example input:
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

Example output:
0
11
4
4
17
60

Editorial:
One operation should be used to remove every element not belonging to $$$T$$$.
Let $$$v$$$ be an element not belonging to $$$T$$$. Suppose a $$$x$$$-cost operation removes value $$$v$$$, then $$$v$$$ must be divisible by $$$x$$$. Furthermore, the multiples $$$x,2x,\cdots (k-1)x$$$ must have been already removed from $$$S$$$, where we write $$$v = kx$$$.
Since removed elements stay removed, the above is only possible if all of $$$x,2x,\cdots (k-1)x$$$ does not belong to $$$T$$$.
For each $$$v$$$, let $$$f(v)$$$ be the smallest integer $$$x$$$ satisfying the above condition. As we can always remove $$$v$$$ using a $$$v$$$-cost operation, $$$f(v) \leq v$$$ and in particular $$$f(v)$$$ exists.
The total cost must be at least $$$\sum_{i \not \in T} f(i)$$$. We claim that this cost can be achieved.
To do so, we should remove the required elements in ascending order. When removing $$$v$$$, we assume all $$$w \not\in T$$$ with $$$w<v$$$ have already been removed. At this state, an $$$f(v)$$$-cost operation would be able to remove $$$v$$$.
It remains to find the values $$$f(v)$$$. To do so efficiently, we can perform the above process in a bottom-up manner similar to the Sieve of Eratosthenes. Please refer to the code below for implementation details. The overall complexity is $$$n (1 +\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}) = O(n \ln n)$$$