• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

HDU 7073 Integers Have Friends 2.0

admin

11月 28, 2021

题意:给n个数,找一个m>=2,使得在模m意义下,相同的数最多

从小的情况开始考虑,如果取m=2,那么最差情况就是n个数一半奇数,一半偶数,答案是n/2,以此类推,最差情况答案是n/m,即n个数均匀分布在模m的剩余系中,那么答案至少是n/2

考虑如何构造比n/2更大的答案,假设已知了答案中的两个数a和b

[a=k_1m+r\
b=k_2m+r
]

相减得

[a-b=(k_1-k_2)m
]

[m|(a-b)
]

设d=abs(a-b),根号枚举d的约数,进行判断,复杂度是(O(nsqrt n))

枚举a、b肯定是不可行的,但注意到答案至少为n/2,即a和b至少有(frac1 4)的概率在答案中,也就是至少有(frac1 4)的概率求出答案,那么进行k次后,我们求得答案的概率就是(1-{(frac{3}{4})}^k),选k=45提交了两次通过

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 200005;

int n;
int a[MAXN], ans;
set<int> st;

void check(int x, int aim) {
	if (st.count(x))
		return;
	int tmp = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] % x == aim)
			tmp++;
	ans = max(ans, tmp);
	st.insert(x);
}

void doit() {
	int rx = rand() % n + 1, ry = rand() % n + 1;
	while (rx == ry)
		ry = rand() % n + 1;
	int d = a[rx] - a[ry];
	if (d < 0)
		d = -d;
	for (int i = 2; i * i <= d; i++) {
		if (d % i)
			continue;
		check(i, a[rx] % i);
		while (d % i == 0)
			d /= i;
	}
	if (d != 1)
		check(d, a[rx] % d);
}

void solve() {
	st.clear();
	scanf("%lld", &n);
	ans = n / 2;
	for (int i = 1; i <= n; i++)
		scanf("%lld", a + i);
	for (int i = 1; i <= 45; i++)
		doit();
	cout << ans << endl;
}

signed main() {
	srand(time(0));
	int T;
	scanf("%lld", &T);
	while (T--)
		solve();
	return 0;
}

本文来自博客园,作者:GhostCai,转载请注明原文链接:https://www.cnblogs.com/ghostcai/p/15158437.html

发表回复

您的电子邮箱地址不会被公开。