Масив Руфо (Розбір)

Розв'язання

Правило перетворення визначає, що для будь-якої пари (a_i, b_i) число $x$ має задовольняти одну з умов: або b_i = x, або b_i = a_i(x-1). Розглянувши перший елемент (a_1, b_1), ми отримуємо не більше двох кандидатів на секретне число: x = b_1 або x = \frac{b_1}{a_1} + 1 (за умови, що b_1 кратне a_1 і x \ge 1). Оскільки $x$ має бути однаковим для всього масиву, перевіряємо, чи породжує хоча б один із кандидатів кожне b_i з a_i за заданою логікою: якщо a_i > x і a_i(x-1) > x, тоді b_i = a_i(x-1); інакше b_i = x. Якщо кандидат задовольняє це для всіх $n$ індексів, то це коректна відповідь; якщо не підходить жоден кандидат, результат дорівнює $-1$.

def ok(x,n,a,b):
	if x<1: return 0
	for i in range(n):
		if a[i]>x and a[i]*(x-1)>x: r=a[i]*(x-1)
		else: r=x
		if r!=b[i]: return 0
	return 1

def solve():
	n=int(input())
	a=list(map(int,input().split()))
	b=list(map(int,input().split()))
	if ok(b[0],n,a,b):
		print(b[0]); return
	if b[0]%a[0]==0:
		x=b[0]//a[0]+1
		if ok(x,n,a,b):
			print(x); return
	print(-1)

t=int(input())
for _ in range(t):
	solve()