ABC125-C GCD on Blackboardを乱択で解いてみた

atcoder.jp

前回のABCで難しいと話題になった上の問題。いろいろ解法があるそうですが、乱択で解いたので紹介します。
また、かなり怪しい解法な気がするので、マサカリも歓迎します。特に、N>10でこの解法を落とせるケース等があれば教えてください。

考え方

与えられた数字の集合を2つの集合に分ける。
集合の一方には取り除くべき数が入っており、その集合の最大公約数は求めたい値以下になる場合がほとんど。
もう一方の集合の最大公約数は、求めたい値以上である。

それぞれの集合の最大公約数を求め、大きい方を採用し、それが解である確率を考える。
確率が低そうなパターンの例は1,2,4,4,4,4,4,4,4...という場合であり、Nが十分に大きい場合には、4が出力される確率が1/2、2が出力される確率が1/2に収束する。 (集合を2つに分けたときに、1と2が同じ集合に含まれる場合と、集合に含まれない場合)

ここで、この操作一度あたりの計算量はNlog(N)であるから、この操作を十分大きな回数行うことができる。

なお、N<=3の場合には答えが出ない場合もあるため、貪欲に計算する。
(例えばN=3,A={6,7,8}など)

ソースコード(抜粋)

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int gcd_of_vector(vector<int> &A, int begin, int end){
  int result = A[begin];
  for(int i=begin;i<end;i++){
    result = gcd(A[i],result);
  }
  return result;
}

//略

  if(N>=100){
    ans=1000000010;
    for(int i=0;i<50;i++){
      random_shuffle(A.begin(),A.end());
      gcd1 = gcd_of_vector(A,0,N/2);
      gcd2 = gcd_of_vector(A,N/2,N);
      ans = min(ans,max(gcd1,gcd2));
    }
  }

//略