题目大意
给定$n$个正整数，从中挑出$k$个数，满足：存在某一个$m(m\ge2)$，使得这$k$个数模$m$的余数相等。
求出$k$的最大值，并求出此时的$m$。如果有多组解使得$k$最大，你要在此基础上求出$m$的最大值。
题目分析
将问题转化一下。
原问题等价于选一个数，让其他数全部减这个数，差值的$\gcd$即为$m$。
预处理一下质数，每次随机选一个数，将差值质因数分解，并顺便求出$\gcd$，边分解边更新答案即可。
因为当$m=2$时，至少选$k$个数。
因此选每个数的概率至少为$\frac 12$，因此随机化很快就能得到较优解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=100005,maxv=10000005,maxp=1000005;
int n,cnt=0,a[maxn],b[maxn],Prime[maxv],lp[maxv],g[maxp],sum[maxp],k=0,m=0;
bool vst[maxv];
void Prime_Table(int n) {
for(int i=2; i<=n; i++) {
if(!vst[i]) {vst[i]=1;Prime[++cnt]=i;lp[i]=cnt;}
for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
vst[i*Prime[j]]=1;
lp[i*Prime[j]]=j;
if(i%Prime[j]==0)break;
}
}
}
int main() {
Prime_Table(10000000);
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int t=1; t<=4; t++) {
int x=a[rand()%n+1];
for(int i=1; i<=n; i++) {
b[i]=abs(a[i]-x);
if(!b[i])sum[0]++;
}
for(int i=1; i<=n; i++) {
int x=b[i];
while(x>1) {
int p=lp[x];
sum[p]++;
g[p]=__gcd(g[p],b[i]);
if(k<sum[p]+sum[0])k=sum[p]+sum[0],m=g[p];
else if(k==sum[p]+sum[0])m=max(m,g[p]);
while(x%Prime[p]==0)x/=Prime[p];
}
}
for(int i=1; i<=n; i++) {
int x=b[i];
while(x>1) {
int p=lp[x];
sum[p]=g[p]=0;
while(x%Prime[p]==0)x/=Prime[p];
}
}
sum[0]=0;
}
printf("%d %d\n",k,m);
return 0;
}
|
