Codeforces Round #822 (Div. 2) C. Removing Smallest Multiples

 iniput:

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

output:

0
11
4
4
17
60

题目大意：给我么一个集合s，s中包含1~n所有数字，现在我们要进行一种操作，操作如下：首先选定一个数字k，在集合中存在k的倍数，然后我们可以删除k的最小的倍数，注意k也是自己的倍数，代价为k，现在给我们一个长度为n的01序列，第i个字符为1表示在进行所有操作之后数字i没有被删除，否则为0就是被删除了，问我们将原来的集合变成现在集合所需要的最小花费是多少？

解题思路：贪心地从小到大枚举每一个数字，对于每一个数字从小到大枚举它的所有倍数，如果一旦发现当前枚举的倍数在最终的集合中没有被删除，那么立即退出，在枚举的时候要一边计算最终的代价和，注意一个数字只能被一个对应的k给删除，我们要避免一个数被多个数字删除的情况，所以对需要删除的数字我们也要记录一下该数字是否在之前已经被删除。

总复杂度NlogN

上代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int t,n,a[N],b[N];
int main() {
	cin>>t;
	while(t--) {
		scanf("%d",&n);
		for(int i=1; i<=n; i++) {
			scanf("%1d",&a[i]);
			b[i]=a[i];//b数组记录数字是否在之前就已经被删除
		}
		long long ans=0;
		for(int i=1; i<=n; i++) {
			for(int j=1; i*j<=n; j++)
				if(a[i*j]==0) {
					if(b[i*j]==0) {
						ans+=i;
						b[i*j]=1;
					}
				} else
					break;
		}
		cout<<ans<<endl;
	}
	return 0;
}