D. Little Pony and Harmony Chest
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 integersa1,?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
51 1 1 1 1
output
1 1 1 1 1
input
51 6 4 2 8
output
1 5 3 1 8
题目大意：
给出N个数ai，求出另一个序列bi，要求sum |ai-bi|，最短，且所有的bi都互质。
解法：
这里题目给了几个很显眼的条件，ai限制在了1~30之间，由于可以bi无限选1这个数，那么|ai-bi| 最大就是29了，意味着bi
要求所有的bi互质，可以化为所有的bi分解出来的质因数均不相同，bi
用s表示当前阶段用了哪些质因数的状态，例如 s = 3 = 11 代表目前状态下使用了第一个和第二个质因数。
很快我们就可以写出状态转移方程：
f[i][s] = min(f[i-1][s^c[k]] + abs(a[i] - k))。 其中c[k]表示数字k使用了哪些质因数。
代码：
#include#include #include #define M_max 60#define N_max 123#define inf 0x3f3f3f3fusing namespace std;int p[N_max], c[M_max], a[N_max];int f[N_max][1