№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
86179859 |
Дорешивание:
JKLover |
364D
- 52
|
C++17 (GCC 7-32)
|
Полное решение
|
3993 мс
|
11960 КБ
|
2020-07-07 10:36:23 |
2020-07-07 10:36:23 |
|
//%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;
}
Время: ? ms, память: ? КБ