题意翻译

题目背景

暮暮正在公主两姐妹的城堡里研究和谐之元的宝箱。

题目描述

对于一个正整数序列bi,当且仅当它的任意两个元素都互质时,这个序列bi才是和谐的。据古书记载,宝箱的钥匙是能让以下表达式的值最小的和谐序列bi:

现在暮暮已经得到了序列ai,你能帮助暮暮找到开启宝箱的钥匙吗?

输入输出格式

输入格式:

第一行包含一个正整数 n (1 ≤ n ≤ 100) ——a、b序列的长度。

第二行包含一串长度为 n 的整数 a1, a2, …, an (1 ≤ ai ≤ 30).

输出格式:

输出仅有一行——满足条件的bi序列。

题意:相当于要求每个数中都不能包含相同的质因数 那么显然a<=30 那么b<=2*a[i]-1 反之b一定不优 还不如选1  那么可以知道60以内的质因数最多有17个所以考虑状压一下

设dp[i][s]表示前i个数选了s状态素数的最优解 设state[i]表示i这个数的质因子的状态 是二进制压位储存的.. 然后转移就直接转移即可 记录pre 便于输出答案

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论