# CFR 364 D. Ghd ( Random, Math )

Problem - D - Codeforces

N ≤ 1e6
A ≤ 1e12

O( ( R=12 ) * N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e6 );

int N;
long long A[ MAXN ];

signed main() {
srand( time( NULL ) );
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ) {
cin >> A[ i ];
}
long long ans = 1;
for( int ti = 0; ti < 12; ++ti ) {
int r = ( rand() << 15 | rand() ) % N;
vector< long long > fac;
for( int i = 0; i < N; ++i ) {
fac.emplace_back( __gcd( A[ r ], A[ i ] ) );
}
sort( fac.begin(), fac.end() );
vector< pair< long long, int > > fc; // factor, count
for( int i = 0; i < N; ++i ) {
if( fc.empty() or fc.back().first != fac[ i ] ) {
fc.emplace_back( fac[ i ], 1 );
} else {
++fc.back().second;
}
}
for( int i = fc.size() - 1; i >= 0; --i ) {
if( ans >= fc[ i ].first ) continue;
int cnt = 0;
for( int j = i; j < fc.size() and cnt * 2 < N; ++j ) {
if( fc[ j ].first % fc[ i ].first == 0 ) {
cnt += fc[ j ].second;
}
}
if( cnt * 2 >= N ) {
ans = fc[ i ].first;
}
}
}
cout << ans << endl;
return 0;
}
```