1734C.md (2454B)
1 Source: https://codeforces.com/problemset/problem/1734/C 2 3 C. Removing Smallest Multiples 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a set $S$, which contains the first $n$ positive integers: $1, 2, \ldots, n$. 22 23 You can perform the following operation on $S$ any number of times (possibly zero): 24 25 * 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$. 26 27 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. 28 29 Input 30 31 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. 32 33 The first line contains a single positive integer $n$ ($1 \le n \le 10^6$). 34 35 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. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$. 38 39 Output 40 41 For each test case, output one non-negative integer — the minimum possible total cost of operations such that $S$ would be transformed into $T$. 42 43 Example 44 45 Input 46 47 ``` 48 6 49 50 6 51 52 111111 53 54 7 55 56 1101001 57 58 4 59 60 0000 61 62 4 63 64 0010 65 66 8 67 68 10010101 69 70 15 71 72 110011100101100 73 ``` 74 75 Output 76 77 ``` 78 0 79 11 80 4 81 4 82 17 83 60 84 ``` 85 86 Note 87 88 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\}$. 89 90 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: 91 92 1. Choose $k=3$, then delete $3$ from $S$. 93 2. Choose $k=3$, then delete $6$ from $S$. 94 3. Choose $k=5$, then delete $5$ from $S$. 95 96 The total cost is $3+3+5 = 11$. It can be shown that this is the smallest cost possible. 97 98 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$. 99 100 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$.