CF1734C Removing Smallest Multiples

给定一个集合 $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$ 所需操作的最小总代价。

在第一个测试用例中，不需要进行任何操作，因为 $S$ 已经等于 $T$，即集合 $\{1, 2, 3, 4, 5, 6\}$。 在第二个测试用例中，初始 $S = \{1, 2, 3, 4, 5, 6, 7\}$，$T = \{1, 2, 4, 7\}$。可以进行如下操作： 1. 选择 $k=3$，删除 $3$； 2. 选择 $k=3$，删除 $6$； 3. 选择 $k=5$，删除 $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$。 由 ChatGPT 4.1 翻译