题目链接：http://codeforces.com/contest/454/problem/D

题意：给定一个序列a， 求一序列b，要求∑|ai−bi|最小。并且b中任意两数的最大公约数为1.

题解：首先要满足最大公约数为1只要控制b中的最小素因数就行。由于a最大之后30，所以加的数肯定不会超过60

如果超过了，直接选择1更小，然后1～60内最多只有17个素数，所以最多状态就是1<<17于是可以考虑一下状压

dp，dp[i][s]表示前i个数拥有素因数的状态为s，然后是转移

x = stat[k] | j 。stat[k]表示的是（k属于1～60.）选择k的限制条件，如果stat[k]&j ！=0就跳过。

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

#include <cmath>

#define inf 0X3f3f3f3f

using namespace std;

const int M = 1e2 + 10;

int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};

int a[M] , dp[M][1 << 17] , stat[61] , num[M][1 << 17] , pre[M][1 << 17] , b[M];

int main() {

    int n;

    scanf("%d" , &n);

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

        scanf("%d" , &a[i]);

    }

    memset(stat , 0 , sizeof(stat));

    for(int i = 2 ; i <= 60 ; i++) {

        for(int j = 0 ; j < 17 ; j++) {

            if(!(i % prime[j])) stat[i] |= (1 << j);

        }

    }

    memset(dp , inf , sizeof(dp));

    dp[0][0] = 0;

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

        for(int j = 0 ; j < (1 << 17) ; j++) {

            if(dp[i][j] == inf) continue;

            for(int k = 1 ; k <= 60 ; k++) {

                if(stat[k] & j) continue;

                int x = (stat[k] | j);

                if(dp[i][j] + abs(a[i + 1] - k) < dp[i + 1][x]) {

                    dp[i + 1][x] = dp[i][j] + abs(a[i + 1] - k);

                    num[i + 1][x] = k;

                    pre[i + 1][x] = j;

                }

            }

        }

    }

    int MIN = inf , pos = 0;

    for(int i = 0 ; i < (1 << 17) ; i++) {

        if(MIN > dp[n][i]) {MIN = dp[n][i] , pos = i;}

    }

    for(int i = n ; i >= 1 ; i--) {

        b[i] = num[i][pos];

        pos = pre[i][pos];

    }

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

        printf("%d " , b[i]);

    }

    printf("\n");

    return 0;

}