/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 700 点
問題文
アオキは数列 a_{1}, a_{2}, ..., a_{N} で遊んでいます。1 秒ごとに、アオキは次の操作を行います。
- 正の整数 k を選ぶ。数列のそれぞれの要素 v について、アオキは v を「v を k で割った余り」に置き換えるか、v をそのままにするかを選べる。この一連の操作のコストは（書き換えた要素の数によらず）2^{k} である。
アオキは、数列を b_{1}, b_{2}, ..., b_{N} に変えたいです（要素の順番も考慮します）。この目的を達成することが可能か判定し、可能である場合は必要な最小のコストを求めてください。
制約
- 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
オーバーフローにご注意。
Score : 700 points
Problem Statement
Aoki is playing with a sequence of numbers a_{1}, a_{2}, ..., a_{N}. Every second, he performs the following operation :
- Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2^{k} (regardless of how many elements he changes).
Aoki wants to turn the sequence into b_{1}, b_{2}, ..., b_{N} (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.
Constraints
- 1 \leq N \leq 50
- 0 \leq a_{i}, b_{i} \leq 50
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N
a_{1} a_{2} ... a_{N}
b_{1} b_{2} ... b_{N}
Output
Print the minimum cost required to turn the original sequence into b_{1}, b_{2}, ..., b_{N}. If the task is impossible, output -1 instead.
Sample Input 1
3 19 10 14 0 3 4
Sample Output 1
160
Here's a possible sequence of operations :
-
Choose k = 7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5, 3, 14.
-
Choose k = 5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0, 3, 4.
The total cost is 2^{7} + 2^{5} = 160.
Sample Input 2
3 19 15 14 0 0 0
Sample Output 2
2
Aoki can just choose k = 1 and turn everything into 0. The cost is 2^{1} = 2.
Sample Input 3
2 8 13 5 13
Sample Output 3
-1
The task is impossible because we can never turn 8 into 5 using the given operation.
Sample Input 4
4 2 0 1 8 2 0 1 8
Sample Output 4
0
Aoki doesn't need to do anything here. The cost is 0.
Sample Input 5
1 50 13
Sample Output 5
137438953472
Beware of overflow issues.