C题

题目链接
出题人题解

解题思维

数论 位运算

• ----(1)

2. ---(2)

对于（1）式 异或和不为0则一定是正数
则缩放不等式有 对于（2）式

对于一个数组其最小公倍数一定是该数组中每一个元素的正整数倍数，有

不妨设 a ≤ b， 则有

注意到 最大值为a
即

又因为
由（6）（7）得
由（3）得 由（8）（9）得

解法

#include "bits/stdc++.h"
using namespace std;
// #define int int64_t

void Solution()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto& x : a) cin >> x;
	sort(a.begin(), a.end());
	int l = 0, r = 0;
	int Res = 0;
	while(l < n)
	{
		while((r < n) && a[r] == a[l]) ++r;
		// cout << "r = " << r << " l = " << l << '\n';
		//奇数个
		if((r - 1 - l + 1) & 1) ++Res;
      	//偶数个
		else Res += 2;

		l = r;
	}
	cout << Res << '\n';
	return;
}
/*
1
0 1
*/

signed main()
{
	ios::sync_with_stdio(false);
    cin.tie(nullptr);

	int t;
	cin >> t;
	while (t--)
	{
		Solution();
	}
	return 0;
}