CFR 364 D. Ghd ( Random, Math )

Problem - D - Codeforces

題意：
給長度 N 的數列 A。問最大的數，使得該數是數列中一半以上的數的因數為何。

制約：
N ≤ 1e6
A ≤ 1e12

解法：
令答案為 g，那麼有一半以上的數字是 g 的倍數。
因此考慮隨機選取一個下標 r，把所有 gcd( A[ r ], A[ i ] ) 算出來。
由於 A[ r ] 的因數再多也不超過 6000，所以這部分可以平方時間算出過半數。
隨機選到正確的下標的機率是 0.5 以上，所以十次全部選錯的機率非常小，是合理的。
最後要注意 rand() 的範圍是 32768。

時間 / 空間複雜度：
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;
}