【日常小测】苹果

题目大意

给定一个长度为$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;
}