fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int N = 1e6 + 5;
  8. int n, a[N];
  9. int lim;
  10.  
  11. namespace sub1 {
  12. void solve() {
  13.     vector<int> p; p.reserve(10000000);
  14.  
  15.     for (int i = 1; i <= n; i++) {
  16.         p.push_back(a[i]);
  17.         for (int j = 2; j * j <= a[i]; j++) {
  18.             if (a[i] % j == 0) {
  19.                 p.push_back(j);
  20.                 if (a[i] / j != j) p.push_back(a[i] / j);
  21.             }
  22.         }
  23.     }
  24.     sort(p.begin(), p.end());
  25.     int ans = 1, pre = 1, cnt = 1;
  26.     for (int c: p) {
  27.         if (c != pre) {
  28.             if (cnt >= lim) ans = pre;
  29.             cnt = 0, pre = c;
  30.         }
  31.         cnt++;
  32.     }
  33.     if (cnt >= lim) ans = pre;
  34.     cout << ans;
  35. }
  36. };
  37.  
  38.  
  39. int isPrime[N], pr[N];
  40. vector<int> primes;
  41. void sieve(int n) {
  42.     isPrime[0] = isPrime[1] = 1;
  43.     for (int i = 2; i <= n; i++) if (!isPrime[i]) {
  44.         pr[i] = i;
  45.         primes.push_back(i);
  46.         for (int j = i * i; j <= n; j += i) if (!isPrime[j]) {
  47.             isPrime[j] = 1;
  48.             pr[j] = i;
  49.         }
  50.     }
  51. }
  52. namespace sub2 {
  53. int cnt[N];
  54. bool checksub() {
  55.     for (int i = 1; i <= n; i++) if (isPrime[a[i]]) return 0;
  56.     return 1;
  57. }
  58. void solve() {
  59.     for (int i = 1; i <= n; i++) cnt[a[i]]++;
  60.     int ans = 1;
  61.     for (int p: primes) {
  62.         if (cnt[p] >= lim) ans = p;
  63.     }
  64.     cout << ans;
  65. }
  66. };
  67. namespace sub3 {
  68. int freq[N], cnt[N];
  69. bool checksub() {
  70.     for (int i = 1; i <= n; i++) if (a[i] > 1000000) return 0;
  71.     return 1;
  72. }
  73. void sieve2(int n) {
  74.     for (int i = 2; i <= n; i++) {
  75.         for (int j = i; j <= n; j += i) cnt[i] += freq[j];
  76.     }
  77. }
  78. void solve() {
  79.     for (int i = 1; i <= n; i++) freq[a[i]]++;
  80.     sieve2(1000000);
  81.     int ans = 1;
  82.     for (int i = 2; i <= 1000000; i++) if (cnt[i] >= lim) ans = i;
  83.     cout << ans;
  84. }
  85. };
  86.  
  87. namespace subfull {
  88. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  89. int randint(int l, int r) {
  90.     return uniform_int_distribution<int> (l, r) (rng);
  91. }
  92. bool check(int x) {
  93.     int cnt = 0;
  94.     for (int i = 1; i <= n; i++) if (__gcd(a[i], x) == x) cnt++;
  95.     return cnt >= lim;
  96. }
  97. void solve() {
  98.     int ans = 1;
  99.     while(clock() < 0.8 * CLOCKS_PER_SEC) {
  100.         int i = randint(1, n), j = randint(1, n);
  101.         int x = __gcd(a[i], a[j]);
  102.         if (check(x)) ans = max(ans, x);
  103.     }
  104.     cout << ans;
  105. }
  106. };
  107. signed main() {
  108.     cin.tie(NULL)->sync_with_stdio(false);
  109.     if(ifstream("RESONANCE.inp")) {
  110.         freopen("RESONANCE.inp", "r", stdin);
  111.         freopen("RESONANCE.out", "w", stdout);
  112.     }
  113.     cin >> n;
  114.     lim = (n + 1)/ 2;
  115.     for (int i = 1; i <= n; i++) cin >> a[i];
  116.     sieve(1000000); 
  117.     // cerr << primes.size();
  118.     // if (sub2::checksub()) return sub2::solve(), 0;
  119.     if (sub3::checksub()) return sub3::solve(), 0;
  120.     if (n <= 100) return sub1::solve(), 0;
  121.     return subfull::solve(), 0;
  122.     return 0;
  123. }
Success #stdin #stdout 0.04s 30272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000
https://ideone.com/87FJag
language:
C++14 (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!