POJ 1777 Vivian 의 문제점(메 이 슨 소수)

전재 출처 를 밝 혀 주 십시오.감사합니다. http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove
제목:K 개수,p1,p2,.......................................................................
http://poj.org/problem?id=1777
여기에 특수 한 소수 가 필요 하 다.메 이 슨 소수.
우 리 는 만족 E=2^i-1 의 소수 E 를 메 이 슨 소수 라 고 부른다.
메 이 슨 소수 에 대해 중요 한 정리 가 있다.'하나의 수 는 몇 개의 중복 되 지 않 는 메 이 슨 소수 의 곱 하기'는'이 수의 약수 와 2 의 멱 차'와 같 지만 중복 할 수 없다.예 를 들 어 3 은 메 이 슨 소수 이 고 9 는 약수 와 2 의 멱 을 만족 시 키 지 못 한다.
또 하나의 중요 한 내용 은 N 의 약수 와 멱 차 는 그것 을 구성 하 는 메 이 슨 소수 의 소스 멱 차 를 직접 더 해서 얻 을 수 있다 는 것 이다.
메 이 슨 소 수 는 매우 적다.문제 가 제시 한 범위 내 에서 8 개의 메 이 슨 소수 만 있 고 시 계 를 쳐 서 열거 한 다음 에 모든 제 시 된 숫자 중 유일 하 게 몇 개의 메 이 슨 소 수 를 가지 고 있 는 지 판단 할 수 있다.어떤 메 이 슨 소수 인자 에 대해 서 는 반드시 하나의 인자 만 있어 야 한다.왜냐하면 전에 말 했 듯 이 9.3*3 에 대해 그 는 만족 하지 않 고 다른 인자 가 있 으 면 만족 하지 않 을 것 이다.
이후 메 이 슨 소수 가 8 개 에 불과 해 상태 압축 DP 를 사용 하면 된다.

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 30
#define inf 1<<29
#define MOD 2007
#define LL long long
using namespace std;
int mason[8]={3,7,31,127,8191,131071,524287,2147483647};
int cnt[8]={2,3,5,7,13,17,19,31};
int dp[1<<8];
int change(int num){
    int ret=0;
    for(int i=0;i<8;i++){
        if(num%mason[i]==0){
            num/=mason[i];
            //        ，  0
            if(num%mason[i]==0)  return 0;
            ret|=1<<i;
        }
    }
    //        ，  0
    if(num!=1)  return 0;
    return ret;
}
int clac(int state){
    int sum=0;
    for(int i=0;i<8;i++)
        if(state&(1<<i))
           sum+=cnt[i];
    return sum;
}
int main(){
    int n,a[100];
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            a[i]=change(a[i]);
            if(!a[i])  i--,n--;
        }
        //        
        if(n==0){
            puts("NO");
            continue;
        }
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<(1<<8);j++)
                if(!(j&a[i]))
                    dp[j|a[i]]|=dp[j];
        }
        int ans=0;
        for(int i=0;i<(1<<8);i++)
            if(dp[i])
                ans=max(ans,clac(i));
        printf("%d
",ans);
    }
    return 0;
}