CF1593D2 Half of Same

质因数分解 枚举

因为答案肯定在 $[0,2\times 10^6]$ 这个区间里面，因此我们可以考虑枚举所有可能的答案并逐一校验。检验时，我们可以枚举 $i$ 让其他 $j\ne i$ 的 $a_j$ 都改变成 $a_i$。时间复杂度为 $\mathcal{O}(k{n}^2)$，但是由于 $k$ 达到了 $2\times 10^6$，因此会超时。

考虑优化校验复杂度。能够发现，当 $a_j>a_i$ 的时候，只需要除可能解的余数一样就行了。因此，我们可以新建一个表用来存余数对应的数量，找到一个数量大于等于 $n/2$ 的余数。时间复杂度为 $\mathcal{O}(kn)$，仍然超时。

这次，我们不再寻找解了，而是枚举 $a_i$ 找到最优解。对于所有 $a_j>a_i$ 的 $a_j$，都可以通过一个数 $x$ 满足 $(a_j-a_i)\mathrm{mod}x=0$ 减到 $a_i$，也就是说可能的 $x$ 必须是 $a_j-a_i$ 的因数。因此，我们先求出所有的因数，存进 map 里面，再找到一个最大的因数 $x$ 满足 $x$ 的数量大于等于 $n/2$ 就行了。时间复杂度 $\mathcal{O}(n^2\sum _{i=1}^n\sqrt{a_i})$。

#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int kMaxN = 45;
 
int a[kMaxN], t, n, ans;
vector<int> v;
unordered_map<int, int> f;
 
unordered_set<int> calc(int x) {
  unordered_set<int> s;
  for (int i = 1; i * i <= x; i++) {
    if (x % i == 0) {
      s.insert(i);
      s.insert(x / i);
    }
  }
  return s;
}
 
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--) {
    cin >> n;
    ans = -1e9;
    for (int i = 1; i <= n; ++i) {
      cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    // 枚举要变成的
    for (int i = 1; i <= n; i++) {
      // 清空
      int times = 0;
      f.clear();
      v.clear();
      // 枚举其他的数
      for (int j = 1; j <= n; j++) {
        if (a[j] == a[i]) {          // 如果大小一样
          times++;                   // 记录数量
        } else if (a[j] > a[i]) {    // 大于 a[i]
          v.push_back(a[j] - a[i]);  // 加入 vector
        }
      }
      // 如果一样的已经超过了 n/2 就有无数种解
      if (times >= n / 2) {
        ans = 1e9;
        continue;
      }
      // 求因数并记录
      for (int i : v) {
        for (int j : calc(i)) {
          f[j]++;
        }
      }
      // 找最大的答案
      for (auto j : f) {
        if (j.second >= n / 2 - times) {
          ans = max(ans, j.first);
        }
      }
    }
    cout << (ans == 1e9 ? -1 : ans) << '\n';
  }
  return 0;
}