【Codeforces 364D】Ghd
随机化
题目大意：
给定一个集合 $S$，要求找到一个子集 $S’$ 满足 $|S’|\geq\frac{|S|}2$，且子集中所有元素的 $\gcd$ 最大。求最大 $\gcd$。
题解：
由于答案集合大小至少为原集合的一半，所以我们随机选择一个数，其在答案集合内的概率为 $\frac 1 2$。
我们考虑选择一个数 $x$，计算出它在答案集合中时，答案最大是多少。
求出 $x$ 的所有因数。由于 $x\leq 10^{12}$，其因数个数最多只有 $6000$ 个左右。这部分复杂度 $O(\sqrt{x})$。
我们计算它和其他数的 $\gcd$，这部分复杂度为 $O(n\log C)$。然后统计其每个因数作为 $\gcd$ 的出现次数。这部分复杂度为 $O(n\log d(x))$。
我们计算 $x$ 的因数 $x’$ 作为 $\gcd$ 最多能选多少个数时，枚举因数中是 $x’$ 倍数的数，将它和它的倍数作为 $\gcd$ 的次数加起来，这些数求 $\gcd$ 能得到不小于 $x’$ 的数。然后判一下是否达到了一半即可。这部分复杂度 $O(d(x)^2)$。
上述算法求出了钦定某个数在答案中的最大答案，时间复杂度是可以接受的。
我们考虑执行 $k$ 次该算法，每次随机一个数，钦定它在答案里，再执行这个算法。
那么算法的错误率为 $\frac{1}{2^k}$。
本题共有 $115$ 个测试点，那么通过所有测试点的概率为 $(\frac{2^k-1}{2^k})^{115}$。
当 $k$ 取过小时可能会出错，当 $k$ 过大时可能会超时。当然可以加一些适当剪枝来提高效率。
我这里取 $k=12$，单组测试点的正确率为 $\frac{4095}{4096}=0.999755859375$，AC 的概率约为 $0.97231096805946504405566011472105$。
如果脸黑可以多交几发手动提高正确率
Code：
#include<iostream>
#include<random>
#include<ctime>
#include<algorithm>
using namespace std;
mt19937 mt(time(0));
const int N=1e6+5;
typedef long long LL;
inline LL gcd(LL a, LL b){
if(!a||!b)return a|b;
register int t=__builtin_ctzll(a|b);
a>>=__builtin_ctzll(a);
do{
b>>=__builtin_ctzll(b);
if(a>b){LL t=b;b=a,a=t;}
b-=a;
}while(b);
return a<<t;
}
LL ans=1;
int n;LL a[N],d[8000],tmp[8000],cnt,tmpc,tot[8000];
void work(LL x){
cnt=tmpc=0;
for(int i=1;(LL)i*i<=x;++i)
if(x%i==0){
d[++cnt]=i;
if(x/i!=i)tmp[++tmpc]=x/i;
}
while(tmpc)d[++cnt]=tmp[tmpc--];
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int T=1;T<=12;++T){
int id=mt()%n+1;
work(a[id]);
for(int i=1;i<=cnt;++i)tot[i]=0;
for(int i=1;i<=n;++i)
++tot[lower_bound(d+1,d+cnt+1,gcd(a[id],a[i]))-d];
for(int i=cnt;i;--i){
if(d[i]<ans)break;
int s=tot[i];
for(int j=i+1;j<=cnt;++j)
if(d[j]%d[i]==0)s+=tot[j];
if(s*2>=n)ans=d[i];
}
}
cout<<ans<<'\n';
return 0;
}