poj 1777 梅森素数

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int d[1000],t,n,dp[10000],cnt[8]={2,3,5,7,13,17,19,31};
int ms[8]={3,7,31,127,8191,131071,524287,2147483647};
int judge(int x){
int res=0;
for(int i=0;i<8;i++){
if(x%ms[i]==0){
res|=(1<<i);
x/=ms[i];
if(x%ms[i]==0)
return 0;
}
}
if(x!=1)
return 0;
return res;
}
int cal(int s){
int res=0;
for(int i=0;i<8;i++){
if(s&(1<<i)) res+=cnt[i];
}
return res;
}
int main(){
while(~scanf("%d",&n)){
for(int i=0;i<n;i++){
scanf("%d",&t);
d[i]=judge(t);
}
int flag=0;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<n;i++){
if(d[i]==0)
continue;
flag=1;
for(int j=0;j<(1<<8);j++)
if(!(j&d[i])) dp[j|d[i]]|=dp[j];
}
if(!flag){
printf("NOn");
continue;
}
int res=0;
for(int i=0;i<(1<<8);i++)
if(dp[i])
res=max(res,cal(i));
printf("%dn",res);
}
}