UVa

Luogu

Vjudge

分析

梅森素数：形如 $2^p-1$ 的素数，其中 $p$ 是素数。

关于梅森素数有一个定理：

$N$ 的约数和能够写成 $2^k\;(k\in\mathbb{N})$ 的充要条件为 $N$ 能够写成一些 $\textbf{互不相同}$ 的梅森素数的积。

于是考虑让 $N$ 为一些不同的梅森素数的积。

对于 $p_i$ ，如果它能够表示为不同的梅森素数的积，就把它保存下来；否则直接忽略掉（对应于 $e_i=0$）。

注意到 $2^{31}$ 范围内只有 $8$ 个梅森素数，于是可以状压每个 $p_i$ 是哪些梅森素数的积。

然后考虑 DP 。设 $dp_S$ 表示是否可以通过一些 $p_i$ 凑出 $S$ 中的梅森素数，转移很简单。

最后遍历所有 $dp_S=1$ 的 $S$ 并算出 $x$ 即可：容易知道这里的 $x$ 就是 $S$ 中梅森素数的 $p$ 的和。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int p[8]={3,7,31,127,8191,131071,524287,2147483647};
const int c[8]={2,3,5,7,13,17,19,31};

inline int check(int x) {
    int res=0;
    for (re int i=0;i<8;++i) {
        if (x%p[i]==0) x/=p[i],res|=(1<<i);
        if (x%p[i]==0) return 0;
    }
    if (x>1) return 0;
    return res;
}

inline int calc(int x) {
    int res=0;
    for (re int i=0;i<8;++i)
        if (x&(1<<i)) res+=c[i];
    return res;
}

int n,a[119],dp[256];

int main() {
    while (scanf("%d",&n)==1) {
        for (re int i=1;i<=n;++i) a[i]=read();
        int top=0;
        for (re int i=1;i<=n;++i) {
            int t=check(a[i]);
            if (t) a[++top]=t;
        }
        n=top;
        if (!n) { puts("NO"); continue; }
        memset(dp,0,sizeof(dp)); dp[0]=1;
        for (re int i=1;i<=n;++i)
            for (re int S=0;S<256;++S)
                if (!(S&a[i])) dp[S|a[i]]|=dp[S];
        int ans=0;
        for (re int S=0;S<256;++S)
            if (dp[S]) ans=max(ans,calc(S));
        printf("%d\n",ans);
    }
    return 0;
}