📝 문제 정보
🧐 관찰 및 접근
- $K$로 나눈 나머지가 같다 = 고른 부분집합의 원소들의 차이가 모두 $K$의 배수이다.
- 그러면? 분위기상 소수만? 신경써도 되는거같다.
- 근데 숫자들의 차이가 $10^9$까지인데… 그러면 너무 많은데 흠
- 근데 일단 직관적으로, $K = 2$일때 비둘기집의 원리에 의해 답은 ${N/2}$ 이상이긴 하다.
- 그리고 직관적으로, 웬만한 경우에 $K$가 작을때 답이 있을 것 같다.
- $K$가 클때를 억지로 만들 수 있나? $K > 1000$ 쯤듸는 어떤 소수라고 하면, 억지로 만들 수 있는 것 같긴 하다.
- 그런데, 이때 $K$가 $N/2$개 이상의 부분집합에 대해 나머지가 같아야하므로, 다르게 말하면 어떤 두 수를 뽑앗을때 50% 이상의 확률로 $K$는 해당 수의 약수이다.
- 랜덤으로 풀 수 있지 않을까?
💻 풀이
void solve(){
auto start = chrono::high_resolution_clock::now();
bitset<32000> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = 0;
rep(i, 2, 32000) if(isPrime[i]){
for(ll j = (ll)i*i; j < 32000; j += i) isPrime[j] = 0;
}
vector<int> primes;
rep(i, 2, 32000) if(isPrime[i]) primes.push_back(i);
int N; cin >> N;
vector<ll> A(N);
rep(i, 0, N) cin >> A[i];
int ans = (N+1)/2;
while(1){
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
if(duration.count() > 900) break;
int a = rand() % N, b = rand() % N;
int diff = abs(A[a] - A[b]);
vector<int> divs;
for(int p: primes){
if(p*p > diff) break;
if(diff % p == 0){
divs.push_back(p);
while(diff % p == 0) diff /= p;
}
}
if(diff > 1) divs.push_back(diff);
for(int d: divs){
map<int, int> mp;
for(auto x: A) mp[x%d]++;
for(auto [_, c]: mp) ans = max(ans, c);
}
}
cout << ans;
}