codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.