题目链接：传送门

Description

给你一个长度为NN的序列a1,a2,...,aNa_1, a_2,...,a_N，你可以进行如下操作：

选择一个正整数kk，对于序列aa中每一个元素可以选择对kk取模也可以什么都不干

无论你选择多少个元素对kk取模，一次操作都要花费2k2^k的代价

问是否能将序列aa变成序列bb，如果可以则输出最小代价

Constraints

1≤N≤50,0≤a,b≤501\le N\le 50, 0\le a,b \le 50

Sample Input

1
2
3
3
19 10 14
0 3 4

Sample Output

1
160

Solution

首先显然能够发现一个性质，因为∑i=0k2i<2k+1\sum_{i=0}^{k}2^i < 2^{k+1}，因此能通过小于等于kk的数满足题意，就一定不用k+1k+1

那么显然我们就能从大到小枚举kk，如果只用k−1k-1的所有数能满足题意的话kk就对答案没有贡献，否则就有贡献

接下来考虑如何Check一个答案是否满足题意

显然只需要建图连边，跑一遍floyd检验连通性即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

#define x first
#define y second
#define x1 X1 
#define x2 X2
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int MaxN = 50 + 5;

int N, A[MaxN], B[MaxN], Dis[MaxN][MaxN];

inline int Check (LL ans)
{
	memset(Dis, 0, sizeof Dis);
	for (int i = 0; i <= 50; ++i) Dis[i][i] = 1;
	for (int i = 1; i <= 50; ++i) if ((1ll << i) & ans) for (int j = 0; j <= 50; ++j) Dis[j][j % i] = 1;
	for (int k = 0; k <= 50; ++k)
		for (int i = 0; i <= 50; ++i)
			for (int j = 0; j <= 50; ++j)
				if (Dis[i][k] && Dis[k][j]) Dis[i][j] = 1;
	for (int i = 1; i <= N; ++i)
		if (!Dis[A[i]][B[i]]) return 0;
	return 1;
}

int main()
{
#ifdef hk_cnyali
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
#endif
	N = read();
	for (int i = 1; i <= N; ++i) A[i] = read();
	for (int i = 1; i <= N; ++i) B[i] = read();
	LL ans = (1ll << 51) - 1; 
	for (int i = 50; i >= 0; --i)
	{
		ans ^= (1ll << i);
		if (!Check(ans)) ans ^= (1ll << i);
	}
	cout<<(ans == ((1ll << 51) - 1) ? -1 : ans)<<endl;
	return 0;
}