Half of Same

Created by LXC on Fri May 19 00:02:17 2023

https://codeforces.com/problemset/problem/1593/D2

ranting: 1900

tag: brute force, math, number theory

题意

给出n个数的数组a（$n\le40,-10^6\le a_i\le 10^6$）。

求一个大于0的整数k使得，让a中每个数增加或减少若干次k后，至少有一半的元素相等。如果这个k可以是无穷大，则输出-1

题解

显然如果本身就有至少一半的元素相等，则输出-1.

否则如果能使得$a_i$和$a_j$相等，
则有$a_i = t_1k+b, a_j = t_2k+b$，$a_i-a_j$是k的倍数。

我们可以花$O(n^2\sqrt C)$时间求出任意两个数的差值绝对值的因子,$C = max(a_i)-min(a_i)$。

我们由大到小枚举这些因子。对于每个因子p，我们尝试将所有其他元素变为$a_i$，看由多少个差值是p的倍数。如果大于一半的元素那么p就是答案

代码

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 1000005
#define MOD 998244353
using namespace std;

int cur = 0;
int ti[N], cnt[N];

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& i : a)
        cin >> i;
    int mx = 0;
    for (int i : a) {
        mx = max(mx, (int)count(a.begin(), a.end(), i));
    }
    if (mx >= n / 2) {
        cout << "-1\n";
        return;
    }
    int sz = max(*max_element(a.begin(), a.end()),
                 abs(*min_element(a.begin(), a.end())));
    set<int, greater<int>> st;
    for (int x : a) {
        for (int y : a) {
            int dif = abs(y - x);
            for (int i = 1; i * i <= dif; i++) {
                if (dif % i == 0)
                    st.insert(i), st.insert(dif / i);
            }
        }
    }
    for (int i : st) {
        for (int x : a) {
            int cnt = 0;
            for (int y : a) {
                if (abs(y - x) % i == 0)
                    cnt++;
            }
            if (cnt >= n / 2) {
                cout << i << "\n";
                return;
            }
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}