UVA1323 Vivian's Problem

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$ 的和。


这题不知道梅森素数完全没法做啊 QAQ

代码

// ===================================
//   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;
}
最后修改:2019 年 11 月 06 日 05 : 13 PM

发表评论