题目链接：https://codeforces.com/contest/453/problem/B
题目大意：对于给定的长度为n的数组{ai}，构造一个长度也为n的数组{bi}，要求数组b中任意两个的元素的最大公因数都为1，并且使得$\sum_{i=1}^{n}\left |a_{i}-b_{i} \right |$最小（n<=100，ai<=30）
思路：
（1）已知ai<=30，所以bi<=2ai - 1<=59，超过2ai - 1的情况显然不如取1更优
（2）手动枚举59以内的所有素数有17个
（3）每个质因子只能被数组b中的一个元素使用，可以用二进制数S描述质因子的使用情况（S表示一个集合），例如数组{8,5,51,1}的S值为100111B（39D），因为质因子2、3、5、17被使用，数组{12,55,8}是非法的（invalid），因为12和8都使用了质因子2
（4）dp[k][S]表示到第k个元素为止，使用质因子情况为S时的最小$\sum_{}^{}\left |a_{i}-b_{i} \right |$值
（5）当bi的取值为j时，j的质因子集合设为Set[j]，~Set[j]表示Set[j]关于全集的补集，对于~Set[j]的任意子集s，有
dp[i][s$\cup $Set[j]]=min(dp[i][s$\cup $Set[j]], dp[i-1][s]+$\left |a_{i}-j \right |$)
代码及注释：
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 #include<iomanip> 5 #include<vector> 6 #include<string> 7 #include<string.h> 8 #include<utility> 9 using namespace std; 10 typedef long long ll; 11 #define el ‘\n‘ 12 const double eps=1e-8; 13 const ll N=998244353; 14 15 //所有用到的质因子 16 int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59}; 17 //全集 18 const int all=(1<<17)-1; 19 //上限 20 const int inf=0x7f7f7f7f; 21 int dp[105][all+5]; 22 int a[105]; 23 int b[105]; 24 int f[65]; 25 int Back[105][all+5]; 26 //计算每个数的质因子集合 27 void init() 28 { 29 for(int i=1;i<=59;i++){ 30 for(int j=0;j<17;j++){ 31 if(i%prime[j]==0){ 32 f[i]|=(1<<j); 33 } 34 } 35 } 36 } 37 38 int main() 39 { 40 ios::sync_with_stdio(false); 41 init(); 42 memset(dp,inf,sizeof(dp)); 43 memset(dp[0],0,sizeof(dp[0])); 44 int n; 45 cin>>n; 46 for(int i=1;i<=n;i++)cin>>a[i]; 47 for(int i=1;i<=n;i++){ 48 //枚举b[i]可能的取值 49 for(int j=1;j<=59;j++){ 50 int uset=~f[j]&all; 51 int state=uset; 52 //枚举所有子集 53 while(state>=0){ 54 state&=uset; 55 if(dp[i-1][state]+abs(a[i]-j)<dp[i][state|f[j]]){ 56 dp[i][state|f[j]]=dp[i-1][state]+abs(a[i]-j); 57 //记录选取的更优值 58 Back[i][state|f[j]]=j; 59 } 60 state--; 61 } 62 } 63 } 64 //根据dp数组逆推数组b的组成 65 int st=0; 66 for(int i=0;i<=all;i++){ 67 if(dp[n][i]<dp[n][st])st=i; 68 } 69 for(int i=n;i>0;i--){ 70 b[i]=Back[i][st]; 71 st^=f[b[i]]; 72 } 73 for(int i=1;i<=n;i++)cout<<b[i]<<‘ ‘; 74 cout<<el; 75 return 0; 76 }
补题：Codeforces Round #259 (Div. 1) B. Little Pony and Harmony Chest