Codeforces Round #748 (Div. 3)

数论 + 随机化

[Problem - D2 - Codeforces](https://codeforces.com/contest/1749/problem/D)

题意

给定一个长度为 \(n\;(1<=n<=40,n为偶数)\) 的数组 \(a\), \(-1e6<=a[i]<=1e6\)

求最大的模数 \(k\), 使得 \(a[i]\) 在模意义下有至少一半个数相等，如果 k 可以无穷大则输出 -1

思路

一开始想暴力枚举值域来验证，妄想能过 \(1e8\) ，但是 TLE 了
其实本题的思路和之前有道 ABC 的题很相似，要保证一半的数在数组里面，那就随机两个位置 u，v，有 \(\frac 14\) 的概率 \(a[u],a[v]\) 在被选中的里面，随机几十次就几乎可以保证至少有一次随机中的 \(a[u],a[v]\) 都确实模意义下相等
如果 \(a[u]\equiv a[v] \pmod k\), 则 \(k\mid abs(a[u]-a[v])\), 枚举因数作为 \(k\) 即可
一次随机的复杂度为 \(\sqrt {值域}*n\)

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 2e6 + 10;

int n;

int a[110], b[110];

int cnt[N];

bool check(int u, int mod)

{

	int ans = 1;

	int uu = (a[u] % mod + mod) % mod;

	for (int i = 0; i < n; i++)

	{

		if (i == u)

			continue;

		int j = (a[i] % mod + mod) % mod;

		if (uu == j)

			ans++;

	}

	return ans >= n / 2;

}

int solve()

{

	map<int, int> mp;

	for (int i = 0; i < n; i++)

	{

		mp[a[i]]++;

		if (mp[a[i]] >= n / 2)

			return -1;

	}

	int t = 100;

	int ans = 1;

	while(t--)

	{

		int u = rand() % n, v;

		while(1)

		{

			v = rand() % n;

			if (u != v)

				break;

		}

		int D = abs(a[u] - a[v]);

		for (int d = 1; d <= D / d; d++)

		{

			if (D % d)

				continue;

			if (check(u, d))

				ans = max(ans, d);

			if (D / d != d && check(u, D / d))

				ans = max(ans, D / d);

		}

	}

	return ans;

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int T;

	cin >> T;

	while(T--)

	{

		cin >> n;

		for (int i = 0; i < n; i++)

			cin >> a[i];

		cout << solve() << endl;

	}

    return 0;

}

巴特西

Codeforces Round #748 (Div. 3) - D2. Half of Same

数论 + 随机化

题意

思路

代码

最新文章

热门文章