題目:給出K個數，p1,p2,……pk,不一定是素數，給這些數添加指數，0-10之間，最終的乘積為n,他的所有因子和為m,問是否存在一個m為2的冪，如果有多個輸出最大的指數，如果沒有輸出NO。
http://poj.org/problem?id=1777
這裡需要用到一種特殊的素數：梅森素數
我們把滿足 E = 2 ^ i - 1 的素數E稱作梅森素數。
關於梅森素數，有一個重要的定理：“一個數能夠寫成幾個不重復的梅森素數的乘積” 等價於 “這個數的約數和是2的冪次”，但是不能重復，比如說3是梅森素數，9就不滿足約數和為2的冪。
還有一個重要內容就是，N的約數和冪次是可以直接由構成它的梅森素數的來源冪次相加而得的。
梅森素數是非常少的，在題目給出的范圍之內，只有8個梅森素數，可以打表列出，然後判斷每一個給出的數中是不是唯一擁有若干個梅森素數。對於某個梅森素數因子，必須只有一個因子，因為之前說過了，對於9.3*3他便 不滿足，而且如果有別的因子肯定也不滿足。
之後由於只有8個梅森素數，使用狀態壓縮DP即可。
[cpp]
#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]) www.2cto.com
ans=max(ans,clac(i));
printf("%d\n",ans);
}
return 0;
}
作者：ACM_cxlove
