[HDU7073] Integers Have Friends 2.0 -随机大法好

2
3
4

ll n,a[maxn];
ll cal(ll x,ll y) {
  ll ret = 0;
  for(int i=1; i<=n; i++) {
    if(a[i] % x == y) ret ++;
  }
  return ret;
}
int main() {
  srand(time(NULL));
  int _ = read;
  while(_ --) {
    n = read;
    for(int i=1; i<=n; i++) a[i] = read;
    ll ans = 1;
    for(int I = 1; I<=30; I++) {
      int p1 = rand() % n + 1;
      int p2 = rand() % n + 1;
      if(p1 == p2) continue;
      ll diff = abs(a[p1] - a[p2]);
      for(ll i=2; 1LL * i * i <= diff; i ++) {
        if(diff % i == 0) {
          while(diff % i == 0) diff /= i;
          ans = max(ans,cal(i,a[p1]%i));
        }
      }
      if(diff > 1) ans = max(ans,cal(diff,a[p1] % diff));
    }
    printf("%lld\n",ans);
  }
  return 0;
}
/**
3
3
10 12 15
4
4 6 9 19
6
2 8 11 15 19 38
**/