DDOSvoid's Blog

2021杭电多校9 H Integers Have Friends 2.0

发表于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7073

简要题意：给定 $n$ 个整数 $a_i$，求一个最打的集合满足存在一个 $m\ge 2$，且这个集合中的数模 $m$​ 同余

$n\le 2\times 10^5,a_i\le 4 \times 10^12$

Solution

我们取 $m=2$，容易得到答案大于等于 $\frac n 2$​

那么我们现在考虑随机两个数 $a[x]$ 和 $a[y]$，那么这两个数在最终答案的集合的概率是 $\frac 1 4$

我们不妨假设这两个数在最终集合中，那么 $m$​ 一定是 $a[x]-a[y]$​ 的质因子，$m$ 只有最多 $11$ 个

因为每次成功的概率只有 $\frac 1 4$​，所以我们需要多枚举几次，大概 $40$​ 次左右即可，这个时候不正确的概率只有 $(\frac{3}{4})^{40}$​，已经足够小了

时间复杂度 $O(40\sqrt a_i+11n)$​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <random>
#define maxn 2000010
#define ll long long
using namespace std;

const int N = 30;

int pri[maxn], cnt; bool isp[maxn]; 
void init_isp(int n) {
    for (int i = 2; i <= n; ++i) { 
        if (!isp[i]) pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}

default_random_engine e(20011203);

int n;
ll a[maxn];

int solve(ll d, ll v) {
    int res = 0; 
    for (int i = 1; i <= n; ++i) res += a[i] % d == v;
    return res; 
}

void work() {
    cin >> n; int ans = 1;
    uniform_int_distribution<int> Rand(1, n);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int o = 1; o <= N; ++o) {
        int x, y; 
        do {
            x = Rand(e);
            y = Rand(e);
        } while (x == y);
        ll d = abs(a[x] - a[y]);
        for (int i = 1; i <= cnt && 1ll * pri[i] * pri[i] <= d; ++i) {
            if (d % pri[i] == 0) ans = max(ans, solve(pri[i], a[x] % pri[i]));
            while (d % pri[i] == 0) d /= pri[i];
        } if (d > 1) ans = max(ans, solve(d, a[x] % d)); 
    } cout << ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; init_isp(2000000);
    while (T--) work();
    return 0; 
}