ACM-ICPC-OJ训练营

问题 D: 删除最小倍数

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 20
[提交][状态][讨论版][命题人:]

题目描述

给你一个集合S，它包含前n个正整数：1,2，…，n。
您可以对S执行以下操作任意次数（可能为零）：
选择一个正整数k，其中1≤k≤n，使得S中存在k的倍数。然后，从S中删除k的最小倍数。此操作需要k的成本。
我们给你一个集合T，它是S的子集。求出最小可能的操作总成本，使S转化为T。我们可以证明这样的转化总是可能的。

输入描述

输入的第一行包含单个整数t（1≤t≤10000）-测试用例的数量。测试用例的描述如下。
第一行包含单个正整数n（1≤n≤1e6）。
每个测试用例的第二行包含一个长度为n的二进制字符串，描述集合T。当且仅当i是T的元素时，字符串的第i个字符为“1”，否则为“0”。
保证所有测试用例的n之和不超过1e6。

输出描述

对于每个测试用例，输出一个非负整数-操作的最小可能总成本，以便将S转换为T。

样例输入

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

样例输出

提示

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

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

选择k=3，然后从S中删除3。

选择k=3，然后从S中删除6。

选择k=5，然后从S中删除5。

总成本为3+3+5=11。可以看出，这是可能的最小成本。

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

在第四个测试用例中，最初，S={1,2,3,4}，T={3}。我们将在k＝1时执行两个操作，删除1和2，然后在k＝2时执行一个操作，以删除4。

[提交][状态]