[HRBUST-1688]数论中的异或（思维题）

数论中的异或

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 75(41 users) Total Accepted: 35(30 users) Rating:  Special Judge: No

Description

给出两集合A和B, 找出最小的非负整数x使得A⊕x=B. 假设A={a1,a2,…,an}, A⊕x={a1⊕x,a2⊕x,…,an⊕x}.⊕代表异或操作

Input

输入的第一行是一个整数T，表示一共有T组测试数据； 对于每组测试数据，第一行是一个整数n代表集合A和B的大小 第二行包含n个整数a1,a2,a3,....an，代表集合A的元素。 第三行包含n个整数b1,b2,b3,....bn，代表集合B的元素。 (1<=n<=100000，n是奇数，0<=ai<2^30)

Output

如果存在x就输出最小的x，如果不存在就输出-1。

Sample Input

1 3 0 1 3 1 2 3

Sample Output

2

不知道是不是数据太水了，我写的AC代码过不了队友写的样例，但是交上后竟然过了。

我的思路：因为数组a和b的数为n个，且n为奇数，那么就去找a和b里面不同的数个数，如果不同数的个数为1，那么结果就是这两个数异或的值，如果超过一个，则输出-1 。

因为数组的元素个数均为奇数，那么两数组去掉非公共数之后肯定能有一个数x，a异或x可以得到b里面的数，而数x就是这两个不相同的数异或得到的。

感觉这样写漏洞好多，比如：如果a，b中有三个不相同的数，但是可以通过a异或数x得到b，这种情况在我的代码里输出是-1，但是应该是存在数x的（没有验证，不知道是不是真的存在）。

欢迎各位大佬留言找到的错误数据

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn=1e6+3;
ll a[maxn],b[maxn];
int main()
{
	int n,t;
	scanf("%d",&t);
	while(t--)
	{
		int sum=0;
		map<int,int>p;
		ll sum1=0;
		ll sum2=0;
		ll sum3=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%lld",&a[i]);
			sum1+=a[i];
			p[a[i]]=1;
		}
		for(int i=0;i<n;i++)
		{
			scanf("%d",&b[i]);
			sum2+=b[i];
			if(p[b[i]]==0) sum+=1;
			else sum3+=b[i];
		}
		if(sum>1) printf("-1\n");
		else
		printf("%lld\n",(sum1-sum3)^(sum2-sum3));
	}
	return 0;
}

正确的代码在这里