You are given a sequence $A=(A_1,A_2,\dots,A_N)$ of length $N$ consisting of positive integers, where the elements of $A$ are distinct. You will choose a positive integer $M$ between $3$ and $10^9$ (inclusive) to perform the following operation once: Can you choose an $M$ so that $A$ satisfies the following condition after the operation? If you can, find such an $M$. Here, an integer $x$ is said to be the majority in $A$ if the number of integers $i$ such that $A_i = x$ is greater than the number of integers $i$ such that $A_i \neq x$.Problem Statement
Constraints
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
If there exists an $M$ that satisfies the condition, print such an $M$. Otherwise, print $-1$.
Sample Input 1
5 3 17 8 14 10
Sample Output 1
7
If you let $M=7$ to perform the operation, you will have $A=(3,3,1,0,3)$, where $3$ is the majority in $A$, so $M=7$ satisfies the condition.
Sample Input 2
10 822848257 553915718 220834133 692082894 567771297 176423255 25919724 849988238 85134228 235637759
Sample Output 2
37
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10
Sample Output 3
-1
首先如果现在就给出一些模某个数同余的数，怎么知道模哪个数同余？设这些数是 \(a_1,a_2\cdots a_k\)，那么两个同余的数一减，一定模的那个数的倍数。所以这些数模 \(\gcd(|a_2-a_1|,|a_3-a_2|,\cdots ,|a_k-a_{k-1}|)\) 一定是同余的，看这个数是否大于2即可。
第二个引理，如果某个数合法，那么他的因数一定合法。这应该是易得的。所以后面的讨论中，我们可以只讨论质数（4也要特殊讨论，由于2被排除在范围外）。
首先对于所有小于等于 \(\sqrt{W}\)(\(W\) 是值域) 的质数，我们可以先跑一次。这里的复杂度不会超过 \(O(\frac{n\sqrt{W}}{\log n})\)。
对于大于 \(\sqrt{W}\) 的质数，应该注意到，如果他合法，那么他选出来的子集中每两个数之差一定都是他的因数。由于选的时候选了超过 \(\lceil\frac n2\rceil\) 个数，所以一定选了原序列中的相邻两个数（除非 \(n\) 为奇数然后跳着选，这个特判一下就好了）。大于 \(\sqrt{W}\) 的质数，在某个数中的所有质因数中至多出现一个。枚举序列的相邻两个数，找到他们的差中那个大于 \(\sqrt{W}\) 的质因数（如果存在的话），然后跑一次看是否合法。分解质因数这里由于我们已经筛出来了小于等于 \(\sqrt{W}\) 的所有质因数，所以可以降到 \(O(\frac{\sqrt{W}}{\log n})\)。注意这里取模加计数要用到哈希表。总复杂度 \(O(\frac{n\sqrt{W}}{\log n})\)
#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=40000,P=5521;
int n,a[N],mx,pri[M],c,p[M],m;
struct hashmap{
int cnt[P],hd[P],idx,nxt[P],val[P];
int insert(int x)
{
if(!hd[x%P])
{
hd[x%P]=++idx;
val[idx]=x;
return ++cnt[idx];
}
for(int i=hd[x%P];i;i=nxt[i])
{
if(val[i]==x)
{
cnt[i]++;
return cnt[i];
}
else if(!nxt[i])
{
nxt[i]=++idx;
val[idx]=x;
cnt[idx]=1;
return 1;
}
}
}
void clear()
{
memset(hd,idx=0,sizeof(hd));
memset(nxt,0,sizeof(nxt));
memset(cnt,0,sizeof(cnt));
}
}cnt;
void check(int i)
{
cnt.clear();
mx=0;
for(int j=1;j<=n;j++)
{
int k=cnt.insert(a[j]%i);
// printf("%d ",a[j]%i);
if(k>mx)
mx=k;
}
// printf("%d\n",mx);
if(mx>n/2)
{
printf("%d\n",i);
exit(0);
}
}
void maxdiv(int x)
{
for(int i=1;i<=m;i++)
while(x%p[i]==0)
x/=p[i];
if(x!=1)
check(x);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
sort(a+1,a+n+1);
for(int i=2;i<=32000;i++)
{
if(!pri[i])
{
p[++m]=i;
for(int j=i;j*i<=32000;j++)
pri[j*i]=1;
}
}
check(4);
for(int i=3;i<=32000;i++)
if(!pri[i])
check(i);
maxdiv(a[3]-a[1]);
for(int i=1;i<=n;i++)
maxdiv(a[i+1]-a[i]);
puts("-1");
}