You are given an integer sequence A=(A_{1}, A_{2},\dots, A_{N}) of length N and an integer M such that 0 ≤ M < \sum\limits_{i=1}^N A_{i}.

An integer sequence B=(B_{1}, B_{2},\dots, B_{N}) of length N is called *good* if:

0 ≤ B_{i} ≤ A_{i} for each 1≤ i ≤ N
B_{1}+ B_{2}+\dots+B_{N}=M

Find the maximum value of \gcd(A_{1}-B_{1},A_{2}-B_{2},\dots,A_{N}-B_{N}) over all good sequences B. Here, \gcd denotes  the [greatest common divisor].

Note: \gcd(a,b,c) = \gcd(a,\gcd(b,c)) and \gcd(a,0)=\gcd(0,a)=a.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N, M.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

------ Output Format ------ 

For each test case, print a single line containing one integer — the maximum value of \gcd(A_{1}-B_{1},A_{2}-B_{2},\dots,A_{N}-B_{N}) over all good sequences B.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$
$0 ≤ M < \sum\limits_{i=1}^N A_{i}$

------ subtasks ------ 

Subtask #1 (50 points): $1 ≤ N ≤ 10^{4}$

Subtask #2 (50 points): Original constraints

----- Sample Input 1 ------ 
4
4 4
1 3 5 7
4 4
5 5 5 5
4 0
4 6 9 12
6 10
15 9 3 8 14 17
----- Sample Output 1 ------ 
3
4
1
7

----- explanation 1 ------ 
Test case $1$: The optimal strategy is to take $B=(1,0,2,1)$. The answer is $\gcd(1-1,3-0,5-2,7-1)=\gcd(0,3,3,6)=3$.

Test case $2$: The optimal strategy is to take $B=(1,1,1,1)$. The answer is $\gcd(5-1,5-1,5-1,5-1)=\gcd(4,4,4,4)=4$.

Difficulty: VERY_HARD
Tags: Number theory

Preprocessing

Mathematics

Starter code:

Solutions:
import math

def divisors(n):
	if n < 2:
		return []
	r = [n]
	nn = int(math.floor(math.sqrt(n)))
	if nn * nn == n:
		r.append(nn)
		nn -= 1
	for i in range(2, nn + 1):
		if n % i == 0:
			r.append(i)
			r.append(n // i)
	r.sort(reverse=True)
	return r
for t in range(int(input())):
	params = input().split()
	N = int(params[0])
	M = int(params[1])
	A = input().split()
	S = -M
	for i in range(N):
		a = int(A[i])
		A[i] = a
		S += a
	A.sort(reverse=True)
	R = 1
	p = 1
	for p in divisors(S):
		s = 0
		for i in range(N):
			a = A[i]
			if a < p:
				break
			m = S - s
			if m > a:
				m = p * (a // p)
			if m * (N - i) < S - s:
				break
			s += m
			if s == S:
				break
		if s == S:
			R = p
			break
	print(R)


def solve(t):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	MAXG = 10 ** 5
	CA = [0] * (2 * MAXG + 1)
	SA = [0] * (2 * MAXG + 1)
	for x in A:
		CA[x] += 1
		SA[x] += x
	for i in range(1, 2 * MAXG + 1):
		CA[i] += CA[i - 1]
		SA[i] += SA[i - 1]
	ans = 1
	for x in range(2, MAXG + 1):
		S = C = 0
		i = 0
		for xx in range(x, MAXG + x + 1, x):
			S += SA[xx - 1] - SA[xx - x] - (CA[xx - 1] - CA[xx - x]) * i * x
			i += 1
		if S <= M and (S - M) % x == 0:
			ans = x
	print(ans)
T = int(input())
for i in range(1, T + 1):
	solve(i)


from bisect import bisect_left
from sys import stdin
input = stdin.readline

def possible(N, M, A, sumA, target):
	index = bisect_left(A, target) - 1
	if index >= 0:
		M -= sumA[index]
		if M < 0:
			return False
	Q = 0
	mult = 1
	while True:
		mult += 1
		index2 = bisect_left(A, mult * target) - 1
		if index2 >= 0 and index2 > index:
			if index == -1:
				q = (index2 + 1) * (mult - 1)
				M -= sumA[index2] - q * target
			else:
				q = (index2 - index) * (mult - 1)
				M -= sumA[index2] - sumA[index] - q * target
			if M < 0:
				return False
			Q += q
			if index2 == N - 1:
				break
			index = index2
	if M % target == 0 and M <= Q * target:
		return True
	else:
		return False

def solve(N, M, A):
	A = sorted(A)
	sumA = list(A)
	for i in range(1, N):
		sumA[i] += sumA[i - 1]
	for i in reversed(range(2, A[-1] + 1)):
		if possible(N, M, A, sumA, i):
			return i
	return 1
T = int(input().strip())
for problem in range(1, T + 1):
	(N, M) = [int(x) for x in input().strip().split()]
	A = [int(x) for x in input().strip().split()]
	print(solve(N, M, A))