AtCoder Beginner Contest 272 - G

随机 + 数论

题意

Submission #35524126 - AtCoder Beginner Contest 272

给一个长度为 \(n\;(1<=n<=5000)\) 的数组 \(a[i]\)，求一个 \(3<=M<=10^9\), 使得有 \(\lfloor\frac {n}{2}\rfloor+1\) 个数在 \(\mod M\) 意义下的值相同

思路

如果随机取两个数，都是那 \(\lfloor\frac {n}{2}\rfloor+1\) 个数的几率是 \(\frac 14\)，因此大概选 1000 次，肯定会有 1 次是都在这一半数里的
对于这两个数 \(x,y\), 若在模 M 意义下相等，则 M 是 \(|x-y|\) 的因子
枚举 \(|x-y|\) 的因子作为 M，\(O(n)\) 检验是否有 \(\lfloor\frac {n}{2}\rfloor+1\) 个数模 M 意义下相同即可
若要进一步优化复杂度，可以只枚举 M 为 \(|x-y|\) 的素因子（如果一个数可以作为 M，那它的因子一定也可以）

但是要注意 M 不能取 2，但可以取 4，要特判 4 可不可以；

这里也要把 2 除干净
```
while(t % 2 == 0)

    t /= 2;

if (t > 1)

    fac.push_back(t);
```

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 5e3 + 10, M = 1e5 + 10;

int a[N];

int n;

int pr[M / 5], cnt;

int p[M];

void get_primes(int n)

{

	p[1] = 1;

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

	{

		if (!p[i])

			pr[++cnt] = i;

		for (int j = 1; j <= cnt && pr[j] <= n / i; j++)

		{

			p[i * pr[j]] = pr[j];

			if (p[i] == pr[j])

				break;

		}

	}

}

int solve()

{

	int tmp[4];

	memset(tmp, 0, sizeof tmp);

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

		tmp[a[i] % 4]++;

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

	{

		if (tmp[i] >= n / 2 + 1)

			return 4;

	}

	int cnt = 10000;

	while(cnt--)

	{

		int u, v;

		u = rand() % n;

		while(1)

		{

			v = rand() % n;

			if (v != u)

				break;

		}

		if (u > v) swap(u, v);

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

		vector<int> fac;

		for (int i = 2; i <= cnt && pr[i] <= t / pr[i]; i++)

		{

			int d = pr[i];

			if (t % d)

				continue;

			while(t % d == 0)

				t /= d;

			fac.push_back(d);

		}

		while(t % 2 == 0)

			t /= 2;

		if (t > 1)

			fac.push_back(t);

		for (auto d : fac)

		{

			int cnt = 2;

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

			{

				if (i == u || i == v)

					continue;

				if (abs(a[i] - a[u]) % d == 0)

					cnt++;

			}

			if (cnt >= n / 2 + 1)

				return d;

		}

	}

	return -1;

}

int main()

{

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

	srand(time(0));

	get_primes(M - 10);

	cin >> n;

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

		cin >> a[i];

	cout << solve() << endl;

    return 0;

}

巴特西

AtCoder Beginner Contest 272 - G - Yet Another mod M

随机 + 数论

题意

思路

代码

最新文章

热门文章