题目大意
给定一个长度为$2n(n \le 100000)$的序列,序列中每个元素$\in [1,10^9]$
让你从中选出$n$个元素,使这$n$个元素的$\gcd$最大
解题报告
我们随机选两个数的话,失败的概率为$\frac{3}{4}$
于是我们选$30 \sim 50$次的话,错误的概率就足够小了
于是我们就随机选几对数,然后求$\gcd$
之后枚举$\gcd$的因数,去更新答案
时间复杂度:$O($跑得过$)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = 1000009; const int TIMES = 30; const double EPS = 0.5; int n,tp,tot,vis[M],pri[M],cnt[N]; LL arr[N],que[N],ans=1; set<LL> VIS; inline LL read() { char c=getchar(); LL f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } LL GCD(LL a, LL b) { return b? GCD(b, a%b): a; } bool DFS(int t, LL v) { if (t > tot) { if (v <= ans || VIS.count(v)) return 1; int ret = 0; VIS.insert(v); for (int i=1;i<=n;i++) ret += (arr[i] % v == 0); if (ret >= (n >> 1)) {ans = v; return 1;} else return 0; } else { bool ret = 0; for (int i=0;i<=cnt[t];i++,v*=que[t]) { if (!DFS(t+1, v)) break; else ret = 1; } return ret; } } int main() { freopen("apple.in","r",stdin); freopen("apple.out","w",stdout); srand(19260817); for (int i=2;i<M;i++) { if (!vis[i]) pri[++tp] = i; for (int j=1;j<=tp&&pri[j]*i<M;j++) { vis[i*pri[j]] = 1; if (i % pri[j] == 0) break; } } n = read(); for (int i=1;i<=n;i++) arr[i] = read(); for (int i=2;i<=n;i++) swap(arr[i], arr[rand()%(i-1)+1]); for (int a,b,kk=1;kk<=TIMES;kk++) { a = rand() % n + 1; b = rand() % n + 1; LL gcd = GCD(arr[a], arr[b]); tot = 0; for (int i=1,v;i<=tp&&(v=pri[i])<=gcd;i++) { if (gcd % v != 0) continue; que[++tot] = v; cnt[tot] = 0; for (;gcd%v==0;++cnt[tot]) gcd /= v; } if (gcd != 1) que[++tot] = gcd, cnt[tot] = 1; DFS(1, 1); } printf("%lld\n",ans); return 0; }