Problem:
 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.

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kai = set()
ans = 0
for m in range(N):
  for i in range(50,0,-1):
    kai.add(i)
  amari = [] 
  for i in kai:
    are = a[m] % i
    amari.append(are)
  for k in range(len(amari)):
    for i in kai:
      are = amari[k] % i
      amari.append(are)
  if b[m] in amari:
    ann = 0
  else:
    ans = -1

for p in range(50,0,-1):
  kai.remove(p)
  for j in range(N):
    amari = [] 
    for i in kai:
      are = a[j] % i
      amari.append(are)
    for k in range(len(amari)):
      for i in kai:
        are = amari[k] % i
        amari.append(are)
    if b[j] in amari:
      ann = 0
    else:
      kai.add(p)
if ans == -1:
   print(-1)
elif a == b:
  print(0)
else:
  ans = 0
  for i in kai:
    ans += 2 ** i
  print(ans)

Solution (Python):
n = int(input())
xs = [int(c) for c in input().split()]
ys = [int(c) for c in input().split()]

def dp(x, y, mods):
  if y > x:
    return False
  table = [False] * (x + 1)
  table[x] = True
  mods.sort(reverse=True)
  for mod in mods:
    for i in range(x + 1):
      table[i % mod] = table[i % mod] or table[i]
  return table[y]

def ok(mods):
  return all(dp(x, y, list(mods)) for x, y in zip(xs, ys))

if not ok(range(1, 51)):
  print(-1)
  quit(0)

mods = []
for mod in range(50, 0, -1):
  if not ok(mods + list(range(1, mod))):
    mods.append(mod)

print(sum(2 ** mod for mod in mods))

Solution (Python):
from collections import deque
N=input()
a=map(int, raw_input().split())
b=map(int, raw_input().split())

S=[]
def bfs(n,start,end):
	c=[set() for i in range(51)]

	for i in range(51):
		for j in range(1,n+1):
	 		c[i].add(i%j)

	for i in range(51):
	 	c[i].add(i)

	for i in range(51):
		for j in S:
			c[i].add(i%j)

	V=[ None for i in range(51) ]

	q = deque([]) 
	V[start]=1
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in c[v]:
			if i==end:
				return True
			else:
				if V[i] is None:
					V[i]=1
					q.append(i)
	else:
		return False



for i in range(50,-1,-1):
	
	for x,y in zip(a,b):
		
		if not bfs(i,x,y):
			if i==50:
				print -1
				quit()
			else:
				S.append(i+1)


ans=0
for i in S:
	ans+=2**i
print ans

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def make_graph(m):
    matrix = np.zeros([m + 1, m + 1, m + 1])
    for k in range(1, m + 1):
        for s in range(k, m + 1):
            matrix[k, s, s % k] = 1
    return matrix


def is_disable(matrix, subset, aaa, bbb):
    if subset:
        sub_matrix = matrix[list(subset)].max(axis=0)
    else:
        sub_matrix = matrix[0]
    sp = floyd_warshall(sub_matrix)
    return any(sp[a, b] > 50 for a, b in zip(aaa, bbb))


def solve(aaa, bbb):
    for a, b in zip(aaa, bbb):
        if a < b:
            return -1
    m = max(aaa)
    matrix = make_graph(m)
    subset = set(range(1, m + 1))
    if is_disable(matrix, subset, aaa, bbb):
        return -1

    for k in range(m, 0, -1):
        subset.remove(k)
        if is_disable(matrix, subset, aaa, bbb):
            subset.add(k)
    return sum(1 << k for k in subset)


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(aaa, bbb))

Solution (Python):
from scipy.sparse.csgraph import dijkstra


def make_graph(m, subset):
    matrix = [[0] * (m + 1) for _ in range(m + 1)]
    for k in subset:
        for s in range(k, m + 1):
            matrix[s][s % k] = 1
    return dijkstra(matrix)


def solve(n, aaa, bbb):
    for a, b in zip(aaa, bbb):
        if a < b:
            return -1
    m = max(aaa)
    subset = set(range(1, m + 1))
    sp = make_graph(m, subset)
    if any(sp[a, b] > 50 for a, b in zip(aaa, bbb)):
        return -1

    for k in range(m, 0, -1):
        subset.remove(k)
        sp = make_graph(m, subset)
        if any(sp[a, b] > 50 for a, b in zip(aaa, bbb)):
            subset.add(k)
    return sum(1 << k for k in subset)


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(solve(n, aaa, bbb))

Solution (Python):
def solve(a, b):
    if a == b:
        yield []
    if a > b:
        for i in range(1, a+1):
            for x in solve(a % i, b):
                yield [i] + x

def subseq(a, b):
    if len(b) == 0: return True
    x = 0
    for t in a:
        if t == b[x]:
            x += 1
            if x == len(b):
                return True
    return False

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

R = []

for i in range(n):
    R.append(list(solve(A[i], B[i])))
    if len(R[-1]) == 0:
        print(-1)
        exit(0)

L = []
answer = 0

for i in range(50, 0, -1):
    T = L + list(range(i - 1, 0, -1))

    ok = True

    for j in range(n):
        cur = False

        for seq in R[j]:
            if subseq(T, seq):
                cur = True
                break

        if not cur:
            ok = False
            break

    if not ok:
        L.append(i)
        answer += 2**i

print(answer)

Solution (Python):

def inpl(): return tuple(map(int, input().split()))

N = int(input())
A = inpl()
B = inpl()
for a, b in zip(A, B):
    if a < b:
        print(-1)
        exit()
        
M = max(max(A), max(B))

S = [i for i in range(1, M+1)]
T = len(S)

def dfs(a, b, G):
    visited = [False]*(M+1)
    Q = [a]
    while Q:
        p = Q.pop()
        if visited[p]:
            continue
        else:
            visited[p] = True
            for q in G[p]:
                if q == b:
                    return True
                if not visited[q]:
                    Q.append(q)
    else:
        return False

found = False
for i in range(M, 0, -1):
    del S[S.index(i)]
    G = [set() for _ in range(M+1)]
    for j in range(1, M+1):
        for s in S:
            G[j].add(j%s)
    
    for a, b in zip(A, B):
        if a==b:
            continue
        if not dfs(a, b, G):
            S.append(i)
            break
    else:
        found = True

ans = 0
for s in S:
    ans += 2**s

if found:
    print(ans)
else:
    print(-1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    aa = LI()
    a = [set([_]) for _ in aa]
    b = LI()

    e = [[None]*51 for _ in range(51)]
    for i in range(51):
        for j in range(i+1):
            if i == j:
                e[i][j] = 0
                continue
            if j == 0:
                e[i][0] = 1
                continue
            for k in range(1,i,1):
                ik = i % k
                if ik == j or ik > j*2:
                    e[i][j] = k
                    break

    for i in range(n):
        if e[aa[i]][b[i]] is None:
            return -1

    def f():
        r = -1
        for i in range(n):
            tr = inf
            for d in a[i]:
                if e[d][b[i]] < tr:
                    tr = e[d][b[i]]
            if r < tr:
                r = tr

        return r

    rr = 0

    while 1:
        k = f()
        if k == 0:
            break
        for i in range(n):
            for c in list(a[i]):
                at = c % k
                if e[at][b[i]] is not None:
                    a[i].add(at)
        rr |= 2**k


    return rr


print(main())

Solution (Python):
from itertools import chain

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

IMP = 100

dp = [[IMP for _ in range(51)] for _ in range(51)]

for i in range(51):
  dp[i][i] = 0
  for j in range(i):
    for m in range(1,51):
      if dp[i%m][j] != IMP:
        dp[i][j] = m
        break


if max(dp[x][y] for x,y in zip(A,B)) == IMP:
  print(-1)
else:
  cost = 0
  m = max(dp[x][y] for x,y in zip(A,B))
  AL = [{a} for a in A]

  def candmin(al,b):
    m = min(dp[a][b] for a in al)
    al.discard(a for a in al if dp[a][b] > m)
    return m

  while m != 0:
    for i,(al,b) in enumerate(zip(AL,B)):
      AL[i] |= set(a%m for a in al)
    cost += 2**m

    m = max(candmin(al,b) for al,b in zip(AL,B))

  print(cost)

Solution (Python):
def pos(a, b, seq):
	st = set([a])
	for k in seq:
		new_st = set(st)
		for v in st:
			new_st.add(v%k)
		st = new_st
	return b in st
	
def main():
	n = input()
	aa = map(int, raw_input().split())
	bb = map(int, raw_input().split())
	def ok(seq):
		for a,b in zip(aa,bb):
			if not pos(a,b,seq):
				return False
		return True
	u = []
	for j in xrange(60,0,-1):
		if not ok(u + range(j-1,0,-1)):
			u.append(j)
	
	if 59 in u:
		print -1
		return
	else:
		print sum(2**k for k in u)

main()