AT_abc134_d Preparing Boxes题解

简述题意

这什么破翻译，看了
AtCoder 的英文才看懂。

给定一个长度为 \(n\) 序列 \(a\)，要求构造一个数列 \(b\)，使得对于任意 \(i\)，满足：

1. \(1 \le i \le n\)

2. 将 \(b\) 序列下标为 \(i\) 的倍数的值相加使得这个总和模 2 等于 \(a_i\)。

求序列 \(b\) 中值为 1 的个数与值为 1 的个数的位置。

解题思路

考虑可以逆序构造序列 \(b\)，因为判断条件只可能用到后面的值。
如果不满足条件 2，则让 \(b_i\) 等于 1，即可满足，并且计入答案；否则为 0.

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>ans;
int n,a[200005],cnt=0,b[200005];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int i=n;i>=1;i--){
		int tmp=0;
		for(int j=i;j<=n;j+=i){
			tmp+=b[j];
		}
		if(tmp%2!=a[i]){
			b[i]=1;
			ans.push_back(i);
		}
	}
	printf("%lld\n",ans.size());
	for(auto x:ans){
		printf("%lld ",x);
	}
	return 0;
}