CF453B Little Pony and Harmony Chest <状压DP>

Problem

Little Pony and Harmony Chest

Description

Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.

A sequence of positive integers is harmony if and only if for every two elements of the sequence their greatest common divisor equals . According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

You are given sequence , help Princess Twilight to find the key.

Input

The first line contains an integer — the number of elements of the sequences and . The next line contains integers .

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Example

Input #1

1 2	5 1 1 1 1 1

Output #1

1 1 1 1 1

Input #2

1 2	5 1 6 4 2 8

Output #2

1 5 3 1 8

标签：状压DP

Translation

题目大意：给出一个个元素的序列，要求找一个个元素的序列，使得中的数两两互质，且要最小化之和。

Solution

对于互质的条件，发现其相当于每个质因子只能用一次（可以用无限次）。发现的范围只有，而如果，则取会更优。因此质因子只可能在之间，只有个，可以状压。
预处理中所有数占用的质因子状态，存在数组中。
表示当前选到第个数，质因子的选择状态为的最大答案。
对于一个数，若，则不能选。
否则有
对于输出方案，存下转移到的状态和选的数，递归输出即可。

Code

#include <bits/stdc++.h>
#define SZ 17
#define MX 60
#define MAX_N 100
#define INF 0x3f3f3f3f
using namespace std;
int pri[SZ] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
int n, a[MAX_N+5], f[MAX_N+5][1<<SZ], g[MAX_N+5][1<<SZ], h[MAX_N+5][1<<SZ], sta[MX];
void init() {
    for (int i = 0; i <= n; i++) for (int j = 0; j < (1<<SZ); j++)
        f[i][j] = INF, g[i][j] = h[i][j] = 0;
    f[0][0] = 0;	memset(sta, 0, sizeof sta);
}
void prt(int i, int j) {if (!i) return;	prt(i-1, g[i][j]), printf("%d ", h[i][j]);}
int main() {
    while (~scanf("%d", &n)) {
        init(); for (int i = 1; i <= n; i++) scanf("%d", a+i);
        for (int i = 2; i < MX; i++) for (int j = 0; j < SZ; j++)
            if (i%pri[j] == 0) sta[i] |= (1<<j);
        for (int i = 0; i < n; i++) for (int j = 0; j < (1<<SZ); j++) {
            if (f[i][j] == INF) continue;
            for (int k = 1; k < MX; k++) {
                if (j&sta[k]) continue;
                if (f[i+1][j|sta[k]] > f[i][j]+abs(a[i+1]-k))
                    f[i+1][j|sta[k]] = f[i][j]+abs(a[i+1]-k), 
                    g[i+1][j|sta[k]] = j, h[i+1][j|sta[k]] = k;
            }
        }
        int pos = -1, ans = INF;
        for (int i = 0; i < (1<<SZ); i++) if (f[n][i] < ans)
            pos = i, ans = f[n][i];
        prt(n, pos), puts("");
    }
    return 0;
}