General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86179859 Practice:
JKLover
364D - 52 GNU C++17 Accepted 3993 ms 11960 KB 2020-07-07 10:36:23 2020-07-07 10:36:23
 
 
→ Source
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(ll x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(ll x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
map<ll, int> mp;
const int N = 1e6 + 10;
int n, m;
ll a[N], ans = 1;
void solve()
{
	mp.clear();
	int x = (rand() << 15 | rand()) % n + 1;
	for (int i = 1; i <= n; ++i)
	{
		ll b = __gcd(a[x], a[i]);
		mp[b]++;
	}
	auto it = mp.end();
	--it;
	while (1)
	{
		ll d = (*it).first;
		if (d <= ans)
			break;
		int cnt = 0;
		for (auto tmp = it; tmp != mp.end() && cnt < m; ++tmp)
			if ((*tmp).first % d == 0)
				cnt += (*tmp).second;
		if (cnt >= m)
			ans = d;
		if (it == mp.begin())
			break;
		--it;
	}
}
int main()
{
	n = read(), m = (n + 1) >> 1;
	for (int i = 1; i <= n; ++i)
		a[i] = read();
	srand(time(0));
	for (int k = 1; k <= 13; ++k)
		solve();
	write(ans, '\n');
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details