「bzoj3837」「Pa2013」Filary - 随机化$+\gcd$ | Bill Yang's Blog

「bzoj3837」「Pa2013」Filary - 随机化$+\gcd$

题目大意

    给定$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++) { //clear
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;
}
姥爷们赏瓶冰阔落吧~
0%