Solution
观察范围 \(a_i\le 30\) 比较特殊，于是我们可以试着考虑 \(b\) 的范围。
直觉告诉我们 \(b\) 不会很大，当 \(b_i\le 59\) 时，有 \(|a_i-b_i|\le 29\)。当 \(b_i > 59\) 时，\(|a_i-b_i|> 29\)，但是如果这时我们将 \(b_i\) 换成 \(1\)，也是满足互质的，且 \(|a_i-b_i|\) 可以变得更小，所以我们可以知道最优答案中 \(b_i\le 59\)。
然后就是经典套路，状压，\(st_i\) 表示 \(i\) 中所含质因子种类，\(f_{i,j}\) 表示前 \(i\) 个数所选的数质因子状态为 \(j\) 的最小答案，转移方程：
\[f_{i,j\oplus st_k}=\min(f_{i-1,j}+|a_i-k|)(st_k \operatorname{and}j=0) \]其中 \(k\) 为第 \(i\) 位选的数。
\([1,59]\) 质数共 \(17\) 个，故 \(j\le 2^{17}-1\)。
需要枚举 \(i,j,k\)，时间复杂度约为 \(O(100\times 2^{17}\times 59)\approx O(7.7\times 10^8)\)。\(4s\) 随便跑。
因为要输出方案，多记一个 \(g_{i,j}\) 表示决策点，并且要用滚动数组可能有点麻烦，建议直接正常写。
Code
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
inline void read(int &x){
char ch=getchar();
int r=0,w=1;
while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
x=r*w;
}
const int N=107,M=2e5+7,inf=1e9;
int a[N],f[N][M],st[N],g[N][M];
int prim[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
int ans[N];
int main(){
int n;read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<=60;i++)for(int j=0;j<=16;j++)
if(i%prim[j]==0)st[i]^=(1<<j);
int S=(1<<17)-1;
memset(f,63,sizeof f);
for(int i=0;i<=S;i++)f[0][i]=0;
for(int i=1;i<=n;i++)for(int j=0;j<=S;j++)for(int k=0;k<=59;k++){
if(st[k]&j)continue;
int tmp=f[i-1][j]+abs(a[i]-k);
if(tmp<f[i][j|st[k]])f[i][j|st[k]]=tmp,g[i][j|st[k]]=k;
}
int res=inf,lst;
for(int i=0;i<=S;i++)if(f[n][i]<res)res=f[n][i],lst=i;
for(int i=n;i>=1;i--)ans[i]=g[i][lst],lst^=st[ans[i]];
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}