做题感悟：本来想水道简单题来，结果这题竟然是状态压缩，想到了分解素因子的方法但是没有想到用状态压缩，因为一看 n 就没状态压缩的想法了，可能状态压缩太弱啊!
解题思路：
因为 ai 不大于 30 ，每个位置都可以放置 1 ，so ~ > bi 应该小于 59 ，因为如果 ai = 30 ,放置 放 1 和放59 是一样的 30 -1 = 59 - 30 所以B数列的数的范围也就确定了，因为B数列的数两两互质，如果用gcd 必定不行，这里可以查看任意两个数是否有素因子，如果有说明不互质，否则互质。从 1 ~ 58 只有16 个素数用状态压缩完全可以，每一位表示一个素数是否存在，然后递推一下就可以了，输出时递归输出即可。
代码：
#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const int INF = 1000000000 ;
const int MY = 59 ;
const int MX = 100 + 10 ;
int num ,n ;
bool flag ;
int prime[MX] ,key[MX] ,g[MX] ,dp[MX][1<<(16)] ;
bool is_prime[MX] ;
void init() // 预处理
{
num = 0 ;
memset(is_prime ,false ,sizeof(is_prime)) ;
for(int i = 2 ;i < MY ;i++)
{
if(!is_prime[i]) prime[num++] = i ;
for(int j = 0 ;j < num && prime[j]*i<MY ;j++)
{
is_prime[i*prime[j]] = true ;
if(i%prime[j] == 0)
break ;
}
}
key[1] = 0 ;
for(int i = 2 ;i < MY ;i++)
{
int K = 0 ;
for(int j = 0 ;j < num ;j++)
{
if(i%prime[j] == 0)
K |= (1<<j) ;
if(i < prime[j]) break ;
}
key[i] = K ;
}
}
void print(int x ,int S) // 递归输出
{
if(!x) return ;
for(int i = 1 ;i < 59 ;i++)
if((S &key[i])==key[i] && dp[x][S] == dp[x-1][S^key[i]] + abs(i - g[x]) && dp[x-1][S^key[i]] != -1)
{
print(x-1 ,S^key[i]) ;
if(flag)
{ cout<<i ; flag =false ; }
else cout<<" "<<i ;
break ;
}
}
void DP()
{
int ans = INF ;
memset(dp ,-1 ,sizeof(dp)) ;
dp[0][0] = 0 ;
for(int i = 1 ;i <= n ;i++)
for(int S = (1<<16)-1 ;S >= 0 ;S--)
for(int j = 1 ;j < 59 ;j++)
if(dp[i-1][S] != -1 && !(S & key[j]))
{
if(dp[i][S|key[j]] != -1)
dp[i][S|key[j]] = min(dp[i][S|key[j]] ,dp[i-1][S] + abs(j-g[i])) ;
else dp[i][S|key[j]] = dp[i-1][S] + abs(j-g[i]) ;
if(i == n)
ans = min(ans ,dp[i][S|key[j]]) ;
}
for(int i = 0 ;i < (1<<16) ;i++)
if(dp[n][i] == ans)
{
flag = true ;
print(n ,i) ;
break ;
}
cout<<endl ;
}
int main()
{
init() ;
while(~scanf("%d",&n))
{
for(int i = 1 ;i <= n ;i++)
scanf("%d",&g[i]) ;
DP() ;
}
return 0 ;
}