分数: 700 点
问题陈述
Aoki 正在玩一系列数字 a_{1}, a_{2}, ..., a_{N}。每一秒,他都会执行以下操作:
- 选择一个正整数 k。对于序列的每个元素 v,青木可能会选择替换 v 及其除以的余数 k,或者不执行任何操作 v。该操作的成本是 2^{k} (无论他改变了多少元素)。
青木想把序列变成 b_{1}, b_{2}, ..., b_{N} (元素的顺序很重要)。确定 Aoki 是否可以执行此任务,如果可以,请找出所需的最低成本。
约束
- 1 \leq N \leq 50
- 0 \leq a_{i}, b_{i} \leq 50
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
a_{1} a_{2} ... a_{N}
b_{1} b_{2} ... b_{N}
输出
打印将原始序列变成所需的最小成本 b_{1}, b_{2}, ..., b_{N}。如果任务不可能完成,则输出 -1 代替。
示例输入 1
3 19 10 14 0 3 4
示例输出 1
160
以下是可能的操作顺序:
-
选择 k = 7。更换 19 与 5, 10 与 3 并且不采取任何措施 14。现在的顺序是 5, 3, 14.
-
选择 k = 5。更换 5 与 0,不执行任何操作 3 并替换 14 与 4。现在的顺序是 0, 3, 4.
总成本为 2^{7} + 2^{5} = 160.
示例输入 2
3 19 15 14 0 0 0
示例输出 2
2
青木可以选择 k = 1 并将一切变成 0。成本是 2^{1} = 2.
示例输入 3
2 8 13 5 13
示例输出 3
-1
这项任务是不可能的,因为我们永远无法转身 8 进入 5 使用给定的操作。
示例输入 4
4 2 0 1 8 2 0 1 8
示例输出 4
0
青木不需要在这里做任何事情。成本是 0.
示例输入 5
1 50 13
示例输出 5
137438953472
注意溢出问题。