题解 CF453B 【Little Pony and Harmony Chest】

思路：数论+状态压缩

这道题的关键条件是：

当且仅当它的任意两个元素都互质时，这个序列bi才是和谐的。

也就是说，我们要让b中的元素两两互质。

很容易想到质数。一个简单的引理是：两个正整数互质，当且仅当它们没有共同的质因数。（证明从略）

因此转化为这n个数均没有相同的质因子。我们再观察，题中a_i的范围非常小，我们猜测在b中出现的质因子不会很大。

定理一：b中的元素所含质因子最大为53。

证明：假设存在b中元素存在>53的质因子，令其为b_i，由质数离散性得b_i\geq 59。将b_i改为1，可知此时一定还是两两互质，且由于a_i\leq 30,|b_i-a_i|=b_i-a_i\geq 59-30=29=30-1\geq a_i-1，矛盾！故命题得证。

同时我们还可以得到一个限定每个元素范围的定理：

定理二：b中每个数均小于59。

证明基本同上，从略。

计算得出[2,53]内的质数共16个，我们可以考虑状态压缩动态规划：设前i个数，能用的质数集合为j的最小值为dp[i][j]，其中j是一个16位二进制数，每一位分别代表一个质数能不能用。

转移方程：

其中k枚举每个决策，table[k]是预先处理好的数组，表示能整除k的质数组成的集合，转移时判断k是否能用集合j中的质数乘出（可用位运算判断），如果能则转移。

另外本题要求输出方案，额外开一个数组way[i][j]存方案即可。

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

int a[101]={};
int dp[101][(1<<16)]={},way[101][(1<<16)]={};

const int prm[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

int table[54]={};

void out(int now_x,int now_y)
{
    if(!now_x)return;
    out(now_x-1,now_y^table[way[now_x][now_y]]);
    printf("%d ",way[now_x][now_y]);
}

int main()
{
    int n=0;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    for(int i=1;i<=58;i++)
    {
        for(int j=0;j<16;j++)
        {
            if(i%prm[j]==0)
            {
                table[i]^=(1<<j);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<(1<<16);j++)
        {
            dp[i][j]=1e9;
            for(int k=1;k<=58;k++)
            {
                if((table[k]|j)!=j)continue;
                int tmp=abs(k-a[i])+dp[i-1][j^table[k]];
                if(tmp<dp[i][j])dp[i][j]=tmp,way[i][j]=k;
            }
        }
    }

    out(n,(1<<16)-1);
}