題目概述

原題參考：B. Make Almost Equal With Mod
給出一個長度為n的數組，可以證明的是，一定存在一個整數k使得a[i]=a[i]%k之后，數組a中只有兩個數，請給出整數k，當然，若有多個k，隨意給出一個即可

思路想法

太巧妙了，本來以為是暴力可以過的，因為其實數組a的很小，最多100個數，當時猜的是對于任意的數，都會存在一個很小的k滿足，就可以直接暴力跑過，但是事實上是錯誤的，還是tle了，因為ai的取值很大，最大是1e18，這里就不得不提到這個問題的解法了
就向題目說的，本題解法與二進制相關，想一下取模運算的幾個例子，123%100=23，1245%1000=245...以這種十進制的取模運算很容易看出來一種截斷效應，當然當k!=10^i次方時是不存在該種現象的，隨便舉幾個二進制的例子，1011%10=1，1001111%100=11，因此二進制取模對2的冪次放也存在截斷效應，這時候我們在判斷一下二進制每一位數有幾種可能，每一位只有兩種可能，當當前位相同時，看下一位，如果不同，那么這一位之后的都想同，這一位不同，正是兩個數，否則如果這一位也相同，那么繼續往下

參考代碼

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 107;
ll n, a[N];
void solve() {
	cin >> n; 
	for(int i=1; i<=n; i++) cin >> a[i];
	set<ll> st;
	ll k = 2;
	while(true) {
		int i;
		for(i=1; i<=n; i++) {
			st.insert(a[i]%k);
			if(st.size() > 2) break;
		}
		if(i == n+1 && st.size() == 2) break;
		else k <<= 1, st.clear();
	}
	cout << k << endl;
	st.clear();
}
int main() {
#ifdef xrl
	freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
	FAST_IO;
	int t = 1;
	cin >> t;
	while(t --) solve();
#ifdef xrl
	cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
	return 0;
}

做題反思

太巧妙了，實在是太好玩了，所以對于任意數組，其實可以通過取模運算變為一個或者兩個數