Codeforces 453 B Little Pony and Harmony Chest(Round 259 div.1 B/div.2 D)

タイトルリンク:http://codeforces.com/contest/454/problem/D
一つの配列aを与えて、もう一つの配列bを要求して、配列bの中のすべての元素の互質を満たして、しかもΣ|ai-bi|(i:0~n)は最小です
配列bの数は1〜60でしか選択できないため、1〜60の質量数配列Sを状態として状態圧縮モデルを構築することができる.dp[i][j]は、前i個数がj状態でΣ|ai-bi|(i:0~n)の最小を満たす値を表す.
コード:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 59
const int INF=0x3f3f3f3f;
using namespace std;
int prime[17],si[61],dp[111][1<<17],mem[111][1<<17],vis[N];
int n,a[111],out[111],pre[111][1<<17];
int pn;
void get_prime()
{
    for(int i=2;i<N;i++)
    {
        if(vis[i]) continue;
        prime[pn++]=i;
        for(int j=i*i;j<60;j+=i)
        {
            vis[j]=1;
        }
    }
}
int tra(int a)
{
    int ans=0;
    for(int i=0;i<pn;i++)
    {
        if(!(a%prime[i])) ans|=(1<<i);
        while(!(a%prime[i])) a/=prime[i];
    }
    return ans;
}
int main()
{
    get_prime();
//    for(int i=0;i<pn;i++)
//        cout<<prime[i]<<' ';
    for(int i=1;i<N;i++)
    {
        si[i]=tra(i);
        //cout<<i<<":"<<si[i]<<endl;
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    int maxn=(1<<pn);
    memset(dp,INF,sizeof(dp));
    memset(dp[0],0,sizeof(dp[0]));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<maxn;j++)
        {
            for(int k=0;k<=60;k++)
            {
                if(!(si[k] & j))
                {
                    int temp=dp[i-1][j]+abs(a[i]-k);
                    if(dp[i][j|si[k]]>temp)
                    {
                        dp[i][j|si[k]]=temp;
                        mem[i][j|si[k]]=k;
                        pre[i][j|si[k]]=j;
                    }
                }
            }
        }
    }
    int ma=INF,ansj;
    for(int i=0;i<maxn;i++)
    {
        if(ma>dp[n][i])
        {
            ma=dp[n][i];
            ansj=i;
        }
    }
    for(int i=n;i>=1;i--)
    {
        int tt=mem[i][ansj];
        out[i]=tt;
        ansj=pre[i][ansj];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d%c",out[i],i==n?'
':' ');
    }
    return 0;
}