Pinely Round 3 (Div. 1 + Div. 2)
B. Make Almost Equal With Mod
题目链接

题意：

给定n和数组a，你可以对数组进行下列操作：

选择一个正整数k，将数组每个元素变为

a

i

%

k

a_i\%k

ai?%k

问k设为什么值可以使得原数组有且仅有两种值

思路：

首先比较容易想到如果原数组有奇有偶的时候直接k=2就行了，如果都是偶数就同时除以

2

x

2^x

2x，使得原数组出现有奇有偶的情况，取k=

2

x

+

1

2^{x+1}

2x+1即可。问题在于全为奇数的时候。

但是既然都是奇数，在mod 2的时候肯定结果都是1，mod 4的时候结果都是1或3，当然也可能全部数mod 4结果都是1（或3），mod 8结果是1、3、5、7，同时余1、5的数在模4的时候都为1，余3、7的数在模4的时候都为3，即当模数乘2的时候，余数相同的数可能会变成两个不同的余数。所以对于都为奇数的情况，我们直接从4开始暴力去试模数，每次乘2即可，n=100很小，而模数每次乘以2所以最多试五六十次，所以可以过。

其实再回来想想，奇数偶数都是一样的，mod 2的时候有可能余数有两种，如果是一种就模数乘2，这样一种余数就有可能变成两种，所以几种情况可以一起来做。

code：

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=105;
typedef long long ll;
 
int T,n;
ll a[maxn];
set<ll> S;
 
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(ll mod=2;mod<=1e18;mod*=2){
			S.clear();
			for(int i=1;i<=n;i++)
				S.insert(a[i]%mod);
			if(S.size()==2){
				cout<<mod<<endl;
				break;
			}
		}
	}
	return 0;
}