题目范围给的很小，所以有状压的方向。
我们是构造出一个数列，且数列中每两个数的最大公约数为1;
给的A[I]<=30，这是一个突破点。
可以发现B[I]中的数不会很大，要不然就不满足，所以B[I]<=60左右。构造DP方程DP[I][J]=MIN(DP[I][J],DP[I][J^C[K]]+abs(a[i]-k));
K为我们假设把这个数填进数组中的数。同时开相同空间记录位置，方便输出结果。。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int cnt=;
int c[],a[];
int dp[][(<<)+];
int pre[][(<<)+][];
int b[]={};
int p[]; void prime()//帅选素数
{
for (int i=;i<;i++)
if (!b[i])
{
p[++cnt]=i;
for (int j=i+i;j<;j+=i)
b[j]=;
}
} int cal(int x)//对每个数分解素数
{
int ans=;
for (int i=;i<=cnt;i++)
{
if (x%p[i]==) ans|=(<<(i-));
while (x%p[i]==) x/=p[i];
}
return ans;
} void print(int x,int pos)//递归出数组
{
if (x==) return;
print(x-,pre[x][pos][]);
cout<<pre[x][pos][]<<" ";
} int main()
{
int n;
prime();
cin>>n;
for (int i=;i<=n;i++) cin>>a[i];
for (int i=;i<;i++)
c[i]=cal(i);
memset(dp,inf,sizeof(dp));
memset(dp[],,sizeof(dp[]));//初始化 for (int i=;i<=n;i++)
for (int j=;j<(<<);j++)
for (int k=;k<;k++)
if ((j&c[k])==c[k]){//由前一个状态推后一个状态
int tmp=dp[i-][j^c[k]]+abs(k-a[i]);
if (dp[i][j]>tmp)
{
dp[i][j]=tmp;
pre[i][j][]=(j^c[k]);
pre[i][j][]=k;
}
} int min=inf,pos;
for (int i=;i<(<<);i++)
if (dp[n][i]<min)
{
min=dp[n][i];
pos=i;
}
print(n,pos);
return ;
}