codeforces 453B Little Pony and Harmony Chest

http://www.elijahqi.win/archives/2871
题意翻译

题目背景

暮暮正在公主两姐妹的城堡里研究和谐之元的宝箱。

题目描述

对于一个正整数序列bi，当且仅当它的任意两个元素都互质时，这个序列bi才是和谐的。据古书记载，宝箱的钥匙是能让以下表达式的值最小的和谐序列bi：

现在暮暮已经得到了序列ai，你能帮助暮暮找到开启宝箱的钥匙吗？

输入输出格式

输入格式：

第一行包含一个正整数 n (1 ≤ n ≤ 100) ——a、b序列的长度。

第二行包含一串长度为 n 的整数 a1, a2, …, an (1 ≤ ai ≤ 30).

输出格式：

输出仅有一行——满足条件的bi序列。

题意：相当于要求每个数中都不能包含相同的质因数 那么显然a<=30 那么b<=2*a[i]-1 反之b一定不优 还不如选1 那么可以知道60以内的质因数最多有17个所以考虑状压一下

设dp[i][s]表示前i个数选了s状态素数的最优解 设state[i]表示i这个数的质因子的状态 是二进制压位储存的.. 然后转移就直接转移即可 记录pre 便于输出答案

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define N 110
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f; 
}
inline int abs(int x){return x<0?-x:x;}
int prime[]={0,2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};
int dp[N][1<<18],state[60],pre[N][1<<18],n,a[N],bin[20];
inline void print(int p,int s){
    if (!p) return;print(p-1,s^state[pre[p][s]]);printf("%d ",pre[p][s]);
}
int main(){
    freopen("cf453b.in","r",stdin);
    n=read();for (int i=1;i<=n;++i) a[i]=read();
    for (int i=0;i<=17;++i) bin[i]=1<<i;const int tot=17;
    memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
    for (int i=1;i<=59;++i)
        for (int j=1;j<=tot;++j)
            if (i%prime[j]==0) state[i]|=bin[j-1];
    for (int i=1;i<=n;++i){
        for (int j=1;j<2*a[i];++j){
            int s=(~state[j])&(bin[tot]-1);
            for (int s1=s;;s1=s&(s1-1)){
                if (dp[i-1][s1]+abs(j-a[i])<dp[i][s1|state[j]]) dp[i][s1|state[j]]=dp[i-1][s1]+abs(j-a[i]),
                pre[i][s1|state[j]]=j;if(!s1) break;
            }
        }
    }int ans=0;
    for (int i=1;i<bin[17];++i) if (dp[n][i]<dp[n][ans]) ans=i;print(n,ans);
    return 0;
}