自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:49:44，当前版本为作者最后更新于2023-08-20 18:22:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先特判 $2|n$ 的情况。可以直接 $x=1$ 然后进行均分。

如果 $x$ 是一个奇数，那么取 $\gcd$ 后会将所有数都变成奇数。而由于 $n$ 是奇数，这样做会导致无解。所以 $x$ 必须为 $2$ 的倍数。

此时，如果序列中仍有 $\gcd(a_i,2)>1$，则将所有数 $/2$，同时将 $x/2$，以此类推。并且，我们希望 $x$ 不要包含多余奇数因子，因为乘上奇数因子后无法改变序列奇偶性。因此，选择 $x=2^{k+1}$，其中 $k$ 是使 $\min\gcd(a_i,2^k)\ge 2^k$ 的最大非负整数。

将 $a_i$ 的所有元素与 $2^{k+1}$ 取 $\gcd$ 方便讨论。此时序列中只有 $1$ 或 $2$。容易发现，如果有奇数个奇数，那么必定无解，原因显然。当存在偶数个奇数时，我们只要将两个 $1$ 相加，构造出一个新的 $2$，就能使 $1$，$2$ 的个数均为偶数，实现均分。

总时间复杂度 $O(n)$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, k, a[MAXN], x[2], y[2], cnt;

int main() {
	scanf("%d", &n), k = 20;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), k = min(k, __lg(a[i] & -a[i]));
	for (int i = 1; i <= n; i++) a[i] >>= k;
	if (~n & 1) {
		puts("1");
		for (int i = 1; i <= n; i++) putchar(i & 1 ? '1' : '0');
	} else {
		for (int i = 1; i <= n; i++) cnt += a[i] & 1;
		if (cnt & 1) return puts("-1"), 0;
		x[0] = y[0] = n - cnt >> 1, x[0]++;
		x[1] = y[1] = cnt >> 1; x[1]--, y[1]++;
		printf("%d\n", 2 << k);
		for (int i = 1; i <= n; i++) putchar(x[a[i] & 1] ? (x[a[i] & 1]--, '0') : '1');
	}
}