51nod 3152 取数游戏

题目链接

我甚至不知道数大小是多少？ 因为要选一半的数，所以每个数被选的概率是\(\frac{1}{2}\)
我们直接随机一个数，它大概率最后会被选。

那么现在只用计算这个数最后被选时，可能的\(\gcd\)是多少。
\(\gcd\)一定是数\(x\) 的一个约数，所以分解\(x\)后求出所有约数。
求出所有\(a-i\)和\(x\)的\(\gcd\)，用桶\(cnt[i]\)记录每个\(\gcd\)出现的次数。
要求每一个约数的\(cnt\)，只需要找到所有的\(d\mid d-i\)，\(cnt-d\text{加上}cnt_{d-i}\)。 而不用每一个数都唯一分解暴力找。
因为对于当前要求的\(cnt-d，\)\(a-i\)和\(x\)的\(\gcd\)无非两种情况
1. \(\gcd(a-i,x)=d\)，这种情况已经记录。
2. 另一种是\(g=\gcd(a-i,x)\)不等于\(d\)，如果\(d\mid g\)，这个\(a-i\)也要记到\(cnt-d\)贡献里面。

注意在算\(cnt\)时的顺序，更新\(cnt_{\gcd}\)以后应该从小的数更新到大的数，不然有可能会算重。因为只能从\(\gcd\)那里更新下来

最后扫一遍\(cnt\)数组，更新所有\(cnt-i\geq\left\lceil\frac{n}{2}\right\rceil\)

假设随机\(k\)次，时间复杂度\(\mathjaxcal{O}(k(n\log a+\sqrt{a}+\sigma(a)^2))\)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 4;
int n, a[N], vis[N], ans, p[N], e[N], tot;
vector<int> v;
unordered-map<int, int> cnt;

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}
void div(int x) {
	tot = 0;
	if (x == 1) {p[++tot] = 1, e[tot] = 1; return;}
	for (int i = 2; i * i <= x; i++) if (x % i == 0) {
		int qaq = 0;
		while (x % i == 0) x /= i, qaq++;
		p[++tot] = i, e[tot] = qaq;
	}
	if (x != 1) p[++tot] = x, e[tot] = 1;
}
void dfs(int x, int res) {
    if (x == tot + 1) {
		v.push-back(res);
		return;
	}
	int now = 1;
	for (int i = 0; i <= e[x]; i++, now = now * p[x]) {
        dfs(x + 1, res * now);
	}
}
void solve(int id) {
    v.clear();
	cnt.clear();
	div(a[id]);
	dfs(1, 1);
    stable-sort(v.begin(), v.end());
	for (int i = 1; i <= n; i++) cnt[gcd(a[id], a[i])]++;
	for (int i = 0; i < v.size(); i++)
		for (int j = i + 1; j < v.size(); j++) {
			if (v[j] % v[i] == 0) cnt[v[i]] += cnt[v[j]];
		}
	for (int i = 0; i < v.size(); i++) if (cnt[v[i]] >= n / 2) ans = max(ans, v[i]);
}

int main() {
	srand(time(0));
    scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int - = 1; - <= min(n, 10); -++) {
		int x = rand() % n + 1;
		while (vis[x]) x = rand() % n + 1;
		vis[x] = 1;
		solve(x);
	}
	printf("%d\n", ans);
	return 0;
}