ABC272G
*2187
我是超级乱搞王.jpg
好像比标算劣但总而言之能过的随机化
题意
给出一个长度为 \(N\) 的序列 \(A\)， 其中 \(A\) 的每个元素均为正整数且互不相同。
你需要选择一个的正整数 \(M\)，满足 \(3\leq M\leq 10^9\)，并执行一次下列操作：
- 对于 \(1\leq i\leq N\)，将 \(A_i\) 替换为 \(A_i\) \(mod\) \(M\)。
若能找到一个数 \(M\) 使得序列 \(A\) 中存在一个数 \(x\)，且对于 \(1\leq i\leq N\)，满足 \(A_i=x\) 的数量大于 \(A_i\) $ ≠$ $ x$ 的数量，输出这个 \(M\)，否则输出 \(-1\)。
题解
“我问他是怎么想到的，他说他考场上瞪了半个小时都不会，觉得这东西不像是有确定性算法的样子。”
—— 一段不知道出处的对话
看到主元素，第一反应是掏摩尔投票，然而这个东西并没有什么打擂台的办法，所以这个是行不通的。
假如存在一个合法的 \(M\) ，那么原序列就可以表示为 \(p\) 个形如 \(k·M+x\) 的数和 \(n-p\) 个不能被如此表示的数。其中 \(2p>n\)，\(x\) 为一个小于 \(M\) 的常数。
那么选取这 \(p\) 个数中的任意两个作差，得到的一定是 \(M\) 的倍数。
还可以证明，如果 \(M\) 是合法的，那么 \(M\) 的任意一个因数也是合法的。
那么我们有了一个简单的想法：枚举两个数 \(u,v\)，相减得到一个初始的 \(M\) ；扫一遍原序列，将枚举到的数与 \(u\) 作差并与 \(M\) 计算 \(\gcd\) ，如果这个 \(\gcd\) 大于 \(3\) 就接受，否则认为扫到的这个数不在 \(p\) 中，跳过。最后检查有多少个数（包括 \(u,v\) ）被接受了，如果满足条件就可以直接打印得到的 \(\gcd\) 了。
时间复杂度 \(O(n^3)\) ，还不能接受。
注意到我们要求解的是主元素，也就是说这个合法集合的大小是大于原序列一半的。如果我们随机地选取两个数，那么这两个数都落在这个合法集合中的概率是 \(25\%\)。
所以我们可以采取随机化的策略，每次随机两个数 \(u,v\)，然后按照上面的方法扫原序列并检查答案。多次随机，如果有解就直接打印答案，反之认为无解即可。
随机的次数可以按照效率来选取。单次扫描原序列是 \(O(n)\) 的，因此我们也可以把随机次数选取在 \(O(n)\) （例如取到 \(5000\)）来使得总效率控制在 \(O(n^2)\) 。而这么做的话误判（即实际有解，但由于运气过于不好导致随机的两个数从来没有同时落入合法集合中）的概率最坏是 \((\frac{3}{4})^{5000}≈5×10^{-3011}\)，完全可以接受。
代码
const ll maxn=5e3+1;
ll a[maxn];
ll n,ans=-1;
void solve(){
srand(time(NULL));
n=R;
for(ll i=1;i<=n;i++)a[i]=R;
for(ll i=1;i<=5000;i++){
ll x=rand()%n+1,y=rand()%n+1;
if(x==y)y=rand()%n+1;
ll bas=abs(a[x]-a[y]);
if(bas<3)continue;
ll cnt=2;
for(ll j=1;j<=n;j++){
if(j==x||j==y)continue;
ll res=__gcd(bas,abs(a[x]-a[j]));
if(res<3)continue;
cnt++,bas=res;
}
if(cnt>n/2){
ans=bas;
break;
}
}
we(ans);
return ;
}