原题链接
题目大意:
给定整数 u 和 v (0\(\leq\)u,v\(\leq\)\(10^{18}\) )试构造长度最短的数组,使得数组内所有元素的异或和为 u,加和为 v。
如果有解,输出两行,第一行输出一个整数 n,第二行输出 n 个非负整数,表示数组里的元素。多解输出任意一组即可。如果无解,输出一行一个整数 −1。
思路:
关于异或的一些性质
根据性质3和4,我们很容易得到
当
- u > v
- u 和 v 的奇偶性不一致
时,无解;
令d = v - u
if (d % 2 == 0), 根据性质1和2,我们很容易得到一组通解{u, \(\frac{d}{2}\), \(\frac{d}{2}\)};
因为序列要最短,所以需要判断一下{ u,d } 和 {u + \(\frac{d}{2}\), \(\frac{d}{2}\)} 符不符合条件;
if (d % 2 != 0), 则无解。
特殊的:若 u == v 则直接输出 u
AC代码
点击查看代码
int n,m;
void solve()
{
cin >> n >> m;
if(n > m) {
cout << -1 << endl; return;
}
int aa = n % 2, bb = m % 2;
if(aa != bb)
{
cout << -1 << endl; return;
}
if(m == 0 && n == 0)
{
cout << 0 << endl; return;
}
int cc = m - n;
if(cc == 0)
{
cout << "1\n" << m << endl;
}
else if(cc % 2 == 0)
{
int d = cc / 2;
if( ((d + n)^d) == n)
{
cout << "2\n" << d+n << " " << d << endl;
}
else if( (cc^n) == n)
{
cout << "2\n" << n << " " << cc << endl;
}
else
{
cout << 3 << endl;
cout << n << " " << d << " " << d;
}
}
else
{
cout << -1 << endl;
}
}