poj 1777梅森素数

能力太水了，下个月的长春邀请赛可怎么办。。。。唉。。。

梅森素数（把形如(2^p-1)形式的素数称为梅森素数，p是素数），挺好的一道题,

1.一个正整数n的所有约数和是2的幂<===>n能够被分解为若干个不同的梅森素数之积。

2.约数和S=(1+p1+p1²+…+p1^a1 )( 1+p2+p2²+…+p2^a2)…(1+pk+pk²+…+pk^ak)

3.输入p1,p2,…,pn,有非梅森素数或非梅森素数的乘积，去掉

	0	1	2	3	4	5	6	7	8
素数指数pr		2	3	5	7	13	17	19	31
mer 2^pr-1		3	7	31	127	8191	131071	524287	2147483647
Hash mer(10)		1	2	4	8	16	32	64	128
Hash mer(2)		1	10	100	1000	10000	100000	1000000	10000000

由于题中给的只有8个数，故任何梅森素数之间的乘积共有2⁸种情况，将状态存在dp[256]中，每个状态保存其约数和的指数。

例如 93 保存为 (100+1)₂=(101)₂=5,dp[5]中，

2*2⁵=2⁶，dp值为6

4.计算出任意dp可生成新的dp值

5.从dp中找一个最大的

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int pr[9]={0,2,3,5,7,13,17,19,31},mer[9]={0,3,7,31,127,8191,131071,524287,2147483647};
 8 int hashh[9]={0,1,2,4,8,16,32,64,128};
 9 int dp[257],prime[300],m;
10 bool visit[257];
11 
12 bool cmp(int a,int b){return a<b;}
13 
14 void ins()
15 {
16     for(int i=1;i<=256;i++)
17         for(int j=1;j<=8;j++)
18             if(i&hashh[j])
19                 dp[i]+=pr[j];
20 }
21 
22 int check(int p)
23 {
24     int ret=0;//在dp中的哪个位置
25     for(int i=1;i<=8;i++)
26     {
27         if(p%mer[i]==0)
28         {
29             p/=mer[i];
30             ret+=hashh[i];
31         }
32         if(p%mer[i]==0) return -1;
33     }
34     if(p>1) return -1;
35     else return ret;
36 }
37 
38 int DP()
39 {
40     memset(visit,0,sizeof(visit));
41     sort(prime+1,prime+m+1,cmp);
42     for(int i=1;i<=m;i++)
43     visit[prime[i]]=1;
44     for(int i=1;i<=256;i++)
45         for(int j=1;j<=m;j++)
46             if(visit[i] && (i & prime[j])==0 && visit[i+prime[j]]==0)//i&prime[i]==0 意为 i 不可能由prime[i]构成
47                 visit[i+prime[j]]=1;
48     int ans=0;
49     for(int i=1;i<=256;i++)
50     if(visit[i] && ans<dp[i]) ans=dp[i];
51     return ans;
52 }
53 int main()
54 {   memset(dp,0,sizeof(dp));
55     ins();
56     int k,a,temp;
57     freopen("in.txt","r",stdin);
58     while(scanf("%d",&k)!=EOF)
59     {
60         m=0;
61         for(int i=1;i<=k;i++)
62         {
63             scanf("%d",&a);
64             temp=check(a);
65             if(temp!=-1)
66                 prime[++m]=temp;
67         }
68         if(m==0)
69         {printf("NO\n");continue;}
70         printf("%d\n",DP());
71     }
72     return 0;
73 }