Removing Smallest Multiples

题意翻译

给定一个集合 $S$，其中包含 $1-n$ 这 $n$ 个数，再给定一个集合 $T$。你可以进行多次操作来将 $S$ 变成 $T$，一次操作可以选择一个正整数 $k$ 并将最小的满足是 $k$ 的倍数并且在集合 $S$ 中的元素删除，删除的代价为 $k$。问将 $S$ 变为 $T$ 的最小代价。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

输出样例 #1

0
11
4
4
17
60

说明

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

**标题：移除最小倍数**

**题意翻译：**
给定一个集合 $ S $，它包含从 $ 1 $ 到 $ n $ 的这 $ n $ 个数，再给定一个集合 $ T $。你可以进行多次操作来将 $ S $ 变成 $ T $，一次操作可以选择一个正整数 $ k $ 并将最小的满足是 $ k $ 的倍数并且在集合 $ S $ 中的元素删除，删除的代价为 $ k $。问将 $ S $ 变为 $ T $ 的最小代价。

**题目描述：**
给定一个集合 $ S $，它包含前 $ n $ 个正整数：$ 1, 2, \ldots, n $。

你可以对 $ S $ 进行任意多次以下操作（可能为零次）：

- 选择一个正整数 $ k $，其中 $ 1 \le k \le n $，使得 $ S $ 中存在 $ k $ 的倍数。然后，从 $ S $ 中删除 $ k $ 的最小倍数。此操作需要 $ k $ 的代价。

给定一个集合 $ T $，它是 $ S $ 的一个子集。找出使得 $ S $ 转换为 $ T $ 的最小可能总操作代价。我们可以证明这样的转换总是可能的。

**输入输出格式：**

**输入格式：**
输入的第一行包含一个整数 $ t $（$ 1 \le t \le 10,000 $）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个正整数 $ n $（$ 1 \le n \le 10^6 $）。

每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串，描述集合 $ T $。字符串的第 $ i $ 个字符是 '1' 当且仅当 $ i $ 是集合 $ T $ 的一个元素，否则为 '0'。

保证所有测试用例的 $ n $ 之和不超过 $ 10^6 $。

**输出格式：**
对于每个测试用例，输出一个非负整数——使得 $ S $ 转换为 $ T $ 的最小可能总操作代价。

**输入输出样例：**

**输入样例 #1：**
```
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100
```

**输出样例 #1：**
```
0
11
4
4
17
60
```

**说明：**
在第一个测试用例中，我们不需要执行任何操作，因为 $ S $ 已经等于 $ T $，即集合 $ \{1, 2, 3, 4, 5, 6\} $。

在第二个测试用例中，最初，$ S = \{1, 2, 3, 4, 5, 6, 7\} $，$ T = \{1, 2, 4, 7\} $。我们将执行以下操作：

1. 选择 $ k=3 $，然后从 $ S $ 中删除 $ 3 $。
2. 选择 $ k=3 $，然后从 $ S $ 中删除 $ 6 $。
3. 选择 $ k=5 $，然后从 $ S $ 中删除 $ 5 $。

总代价是 $ 3+3+5 = 11 $。可以证明这是可能的最小代价。

在第三个测试用例中，最初，$ S = \{1, 2, 3, 4\} $，$ T = \{\} $（空集）。我们将执行 $ 4 $ 次 $ k=1 $ 的操作来删除 $ 1 $, $ 2 $, $ 3 $, 和 $ 4 $。

在第四个测试用例中，最初，$ S = \{1, 2, 3, 4\} $，$ T = \{3\} $。我们将执行两次 $ k=1 $ 的操作来删除 $ 1 $ 和 $ 2 $，然后执行一次 $ k=2 $ 的操作来删除 $ 4 $。**标题：移除最小倍数** **题意翻译：** 给定一个集合 $ S $，它包含从 $ 1 $ 到 $ n $ 的这 $ n $ 个数，再给定一个集合 $ T $。你可以进行多次操作来将 $ S $ 变成 $ T $，一次操作可以选择一个正整数 $ k $ 并将最小的满足是 $ k $ 的倍数并且在集合 $ S $ 中的元素删除，删除的代价为 $ k $。问将 $ S $ 变为 $ T $ 的最小代价。 **题目描述：** 给定一个集合 $ S $，它包含前 $ n $ 个正整数：$ 1, 2, \ldots, n $。 你可以对 $ S $ 进行任意多次以下操作（可能为零次）： - 选择一个正整数 $ k $，其中 $ 1 \le k \le n $，使得 $ S $ 中存在 $ k $ 的倍数。然后，从 $ S $ 中删除 $ k $ 的最小倍数。此操作需要 $ k $ 的代价。 给定一个集合 $ T $，它是 $ S $ 的一个子集。找出使得 $ S $ 转换为 $ T $ 的最小可能总操作代价。我们可以证明这样的转换总是可能的。 **输入输出格式：** **输入格式：** 输入的第一行包含一个整数 $ t $（$ 1 \le t \le 10,000 $）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个正整数 $ n $（$ 1 \le n \le 10^6 $）。 每个测试用例的第二行包含一个长度为 $ n $ 的二进制字符串，描述集合 $ T $。字符串的第 $ i $ 个字符是 '1' 当且仅当 $ i $ 是集合 $ T $ 的一个元素，否则为 '0'。 保证所有测试用例的 $ n $ 之和不超过 $ 10^6 $。 **输出格式：** 对于每个测试用例，输出一个非负整数——使得 $ S $ 转换为 $ T $ 的最小可能总操作代价。 **输入输出样例：** **输入样例 #1：** ``` 6 6 111111 7 1101001 4 0000 4 0010 8 10010101 15 110011100101100 ``` **输出样例 #1：** ``` 0 11 4 4 17 60 ``` **说明：** 在第一个测试用例中，我们不需要执行任何操作，因为 $ S $ 已经等于 $ T $，即集合 $ \{1, 2, 3, 4, 5, 6\} $。 在第二个测试用例中，最初，$ S = \{1, 2, 3, 4, 5, 6, 7\} $，$ T = \{1, 2, 4, 7\} $。我们将执行以下操作： 1. 选择 $ k=3 $，然后从 $ S $ 中删除 $ 3 $。 2. 选择 $ k=3 $，然后从 $ S $ 中删除 $ 6 $。 3. 选择 $ k=5 $，然后从 $ S $ 中删除 $ 5 $。 总代价是 $ 3+3+5 = 11 $。可以证明这是可能的最小代价。 在第三个测试用例中，最初，$ S = \{1, 2, 3, 4\} $，$ T = \{\} $（空集）。我们将执行 $ 4 $ 次 $ k=1 $ 的操作来删除 $ 1 $, $ 2 $, $ 3 $, 和 $ 4 $。 在第四个测试用例中，最初，$ S = \{1, 2, 3, 4\} $，$ T = \{3\} $。我们将执行两次 $ k=1 $ 的操作来删除 $ 1 $ 和 $ 2 $，然后执行一次 $ k=2 $ 的操作来删除 $ 4 $。