Vivian's Problem UVA - 1323(梅林素数+状压二进制)

借鉴：https://blog.csdn.net/miku23736748/article/details/52135932

https://blog.csdn.net/acm_cxlove/article/details/7860735

题意：给定k个数，然后为每个数添加一个幂ei（0=<ei<=10），最后k项累乘的结果为M，如果M的所有因子的和可以写成2^x,求x的最大值，如果没有条件满足，输出NO

我们把满足 E = 2 ^ i - 1 的数称为梅林数 E如果是素数则为梅森素数。

关于梅森素数，有一个重要的定理：“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”，但是不能重复，比如说3是梅森素数，9就不满足约数和为2的幂次。因为9 = 3 * 3 3重复了所以9就不是2的幂次

并且这个2的幂（指数）正好等于作为因子的梅森素数的梅森指数的和。

而 3 (2的2次幂-1) X 7 (2的3次幂-1) = 21;

21的因数和1+3+7+21=32=2^5; 这个 2的幂 5 = 2 + 3；

所以本题的解题思路就出来了

对于每一个输入的数我们去判断是否为几个不重复的梅林素数的乘积组成的

如果不是则把这个数的e置为0 所以就不用考虑它了

如果是我们就用二进制去记下它是由那几个梅林素数组成的这里我们记下的是梅林素数在数组中的下标也是对应梅林素数的梅林指数在相应数组中的下标因为都一一对应

然后我们遍历这些这些下标。。。用dp数组标记这些下标和可以由这些下标组成的另一些下标而且这另一些下标还得必须是输入的那几个数所产生的

这句话什么意思呢。。。就是看看组成输入的这几个数的梅林素数是否有重复没有就合并

最后通过标记累加梅林素数的梅林指数求出最大值即可

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int mason[]={,,,,,,,};  //梅林素数

int ans[]={,,,,,,,};   //梅林素数对应的梅林指数

int dp[<<];

int check(int k)

{

    int cnt = ;

    for(int i=; i<; i++)

    {

        if(k % mason[i] == )

        {

            cnt |= <<i;

            k /= mason[i];

        }

        if(k % mason[i] == )

        {

            return ;

        }

    }

    if(k > )

        return ;

    return cnt;

}

int cal(int x)

{

    int res = ;

    for(int i=; i<; i++)

        if(x & (<<i))

            res += ans[i];

    return res;

}

int main()

{

    int n, a[];

    while(~scanf("%d",&n))

    {

        mem(a, );

        mem(dp, );

        for(int i=; i<n; i++)

        {

            int w;

            scanf("%d",&w);

            int temp = check(w);

            if(!temp) i--, n--;

            else a[i] = temp;

        }

        if(n == )

        {

            cout<< "NO" <<endl;

            continue;

        }

        dp[] = ;

        for(int i=; i<n; i++)

            for(int j=; j< <<; j++)

                if(!(j & a[i]))     //判断两个数的梅林素数是否重复

                    dp[j|a[i]] |= dp[j];　　//j|a[i] 第一次是否被标记却决于dp[j] 因为a[i]肯定有 但不知道j是否有 这样想 = 就可以 但为什么是 |= ，以为如果另一对j|a[i]的值与这对相同 而这对的j存在 另一对的j不存在 如果是=就会被置为零 所以用|=

        int maxx = -INF;

        for(int i=; i< <<; i++)

        {

            if(dp[i])

                maxx = max(maxx, cal(i));

        }

        cout<< maxx <<endl;

    }

    return ;

}

巴特西

Vivian's Problem UVA - 1323(梅林素数+状压二进制)

最新文章

热门文章