【cf453B】Little Pony and Harmony Chest

2014年8月2日1,5490

Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.

A sequence of positive integers bi is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

You are given sequence ai, help Princess Twilight to find the key.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of elements of the sequences a and b. The next line contains n integers a1, a2, …, an (1 ≤ ai ≤ 30).

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Sample test(s)
input

output

input

output

题解

一开始以为是相邻互质。。。后来发现过不了样例T T

如果相邻互质直接dp即可

大概这样

两两互质就比较麻烦了

首先1-60的质数有17个,去掉59,因为取59不如取1

那么就剩下16个,状压一下T T,转移枚举使用了那个数字,应该要预处理下每个数字用了哪些质因数吧T T,不然似乎比较虚

复杂度2^16*100*60是三亿多,在cf的机子下并且非常多废状态还是妥妥过的啦

我最大的点似乎只跑一秒左右。。。时限是4秒啊