poj 1777 Vivian's Problem

题意：给出K个数，p1,p2,……pk,不一定是素数，给这些数添加指数，0-10之间，最终的乘积为n,他的所有因子和为m,问是否存在一个m为2的幂，如果有多个输出最大的指数，如果没有输出NO。

梅森素数 

我们把满足 E = 2 ^ i - 1 的素数E称作梅森素数。
关于梅森素数，有一个重要的定理：“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”，但是不能重复，比如说3是梅森素数，9就不满足约数和为2的幂。
还有一个重要内容就是，N的约数和幂次是可以直接由构成它的梅森素数的来源幂次相加而得的。

给定k个数，p1,p2...pk,计算n=p1^e1*p2^e2*...*pi^ei*...*pk^ek (0<=ei<=10, no all ei==0)

m是n的因子和，如果m是2的幂指数次即存在x使得m=2^x，求最大的x，不存在输出NO

把n写成质因子的幂指数乘积，底数均为质数，n=x1^a1*x2^a2....（任何数都可以写成质数相乘的形式）

m=(1+x1+x1^2...x1^a1)*(1+x2+x2^2...x2^a2)....要使得m=2^x,显然a1,a2,a3...都必须为1

（解释上一句：因为x为质数，所以x^a的因子就只有1，x,x^2...x^a，而每个x^a都有这样的因子，他们的因子相乘同样也是n的因子，因此要将所有的值都算进来，因此将每个x^a的因子和都相乘就可以得到n的总因子和。因为m=2^x，所以（1+x+x^2+...+x^a）= 2^x1，那么2^x1 - 1 =(x+x^2+...+x^a)，而x，2^x1 - 1为质数，所以如果a>1的话，(x+x^2+...+x^a)就可以提出一个x出来就一定不是素数了，所以a必须为1）

那么x1,x2,x3就必须为梅森数了，对于输入的数只能是若干不同的梅森素数的积，如果某个数不是，那么把他踢出掉（相当于e= 0，即p^0=1）

标记下它能够组合的状态，找个和最大的即可 

梅森素数是非常少的，在题目给出的范围之内，只有8个梅森素数，可以打表列出，然后判断每一个给出的数中是不是唯一拥有若干个梅森素数。对于某个梅森素数因子，必须只有一个因子，因为之前说过了，对于9.3*3他便 不满足，而且如果有别的因子肯定也不满足。
之后由于只有8个梅森素数，使用状态压缩DP即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define MAXN 256
#define E exp(1.0f)
#define min 0.0000001
const int mi = 19931117;
int mersenne[8] = { (1 << 2) - 1, (1 << 3) - 1, (1 << 5) - 1, (1 << 7) - 1, (1 << 13) - 1,(1 << 17) - 1, (1 << 19) - 1, (1 << 31) - 1 };
int pwr[8] = {2, 3, 5, 7, 13, 17, 19, 31};
int sum[MAXN];
int a[MAXN];
bool used[MAXN];

void init(){
    for(int i = 0; i < 256; i++){
        sum[i] = 0;
        for(int j = 0; j < 8; j++){
            if(i & (1<<j)){
                sum[i] += pwr[j];//计算出状态压缩的这个数i里含有的梅森素数的指数和
            }
        }
    }
}

int change(int x){//计算出它所包含的梅森素数的个数，返回组成它的所有梅森素数的指数和（状态压缩了的指数和）
    int ret = 0;
    for(int i = 0; i < 8; i++){
        if(x % mersenne[i] == 0){
            x /= mersenne[i];
            if(x % mersenne[i] == 0)return -1;
            ret |= 1 <<i;
        }
    }
    if(x != 1)return -1;
    return ret;
}


int main() {
    int n,c, cnt, p, ans, k;
    init();
    while(~scanf("%d",&n)) {
        memset(used,0,sizeof(used));
        used[0] = 1;
        for(int i = 1; i <= n; i++){
            scanf("%d",&p);

            p = change(p);
            if(p == -1)continue;

            for(int j = 0; j < 256; j++){//根据求出的状态压缩的梅森素数，组合各个值，将能组合出来的值全部标记，因为梅森素数不能相同，所以用异或来得出
                if((j & p )== p&& used[p^j] == 1){//i里面包含了p，而i-p之后剩下的数，可以由其它的梅森素数组成，因此i可以通过p和其它梅森素数组成
                    used[j] = 1;//因为p和i的范围都是256，所以具有相反性，前面没有出现的情况，后面一定会出现
                }
            }


        }
            ans = 0;
            for(int j = 0; j < 256; j++){
                if(used[j] && ans < sum[j]){
                    ans = sum[j];
                }
            }
            if(ans == 0)printf("NO\n");
            else
            printf("%d\n",ans);

    }
    return 0;
}

参考文章：

http://www.2cto.com/kf/201208/147819.html