Nezzar and Board (Codeforces 1478D)
Tags: Math, number theory

$$$n$$$ distinct integers $$$x_1,x_2,\ldots,x_n$$$ are written on the board. Nezzar can perform the following operation multiple times.  Select two integers $$$x,y$$$ (not necessarily distinct) on the board, and write down $$$2x-y$$$. Note that you don't remove selected numbers. Now, Nezzar wonders if it is possible to have his favorite number $$$k$$$ on the board after applying above operation multiple times.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The first line of each test case contains two integers $$$n,k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$-10^{18} \le k \le 10^{18}$$$).The second line of each test case contains $$$n$$$ distinct integers $$$x_1,x_2,\ldots,x_n$$$ ($$$-10^{18} \le x_i \le 10^{18}$$$).It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print "YES" on a single line if it is possible to have $$$k$$$ on the board. Otherwise, print "NO".You can print each letter in any case (upper or lower).

Note: In the first test case, the number $$$1$$$ is already on the board.In the second test case, Nezzar could perform the following operations to write down $$$k=0$$$ on the board:   Select $$$x=3$$$ and $$$y=2$$$ and write down $$$4$$$ on the board.  Select $$$x=4$$$ and $$$y=7$$$ and write down $$$1$$$ on the board.  Select $$$x=1$$$ and $$$y=2$$$ and write down $$$0$$$ on the board. In the third test case, it is impossible to have the number $$$k = -1$$$ on the board.

Sample Inputs:
6
2 1
1 2
3 0
2 3 7
2 -1
31415926 27182818
2 1000000000000000000
1 1000000000000000000
2 -1000000000000000000
-1000000000000000000 123
6 80
-5 -20 13 -14 -2 -11

Sample Outputs:
YES
YES
NO
YES
YES
NO

Solution (Python):
import math
import bisect
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
r = 1

def judge(num, d):
    if num >= 10 * d:
        return True
    while num > 0:
        if num % 10 == d:
            return True
        num -= d
    return False
while r <= T:
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    arr = sorted(arr)
    loc = bisect.bisect_left(arr, k)
    if loc == n:
        target = k - arr[-1]
    elif loc == 0:
        target = arr[0] - k
    else:
        target = k - arr[loc]
    distance = []
    for i in range(n - 1):
        distance.append(arr[i + 1] - arr[i])
    distance = sorted(distance)
    begin = distance[0]
    ans = 'NO'
    if target % begin == 0:
        ans = 'YES'
    else:
        for i in range(n - 2):
            begin = math.gcd(begin, distance[i + 1])
            if begin == 1 or target % begin == 0:
                ans = 'YES'
                break
    print(ans)
    r += 1

Solution (Python):
import math
import operator as op
from functools import reduce
from math import comb
NO = 'NO'
YES = 'YES'
MOD = 1000000007

def input_int():
    return int(input())

def input_list():
    return input().split(' ')

def input_list_int():
    return list(map(int, input_list()))

def z_func(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def ncr(n, k):
    k = min(k, n - k)
    t = reduce(op.mul, range(n, n - k, -1), 1)
    b = reduce(op.mul, range(1, k + 1), 1)
    return t // b
ans = []

def p(line):
    ans.append(line)

def solve():
    (n, k) = input_list_int()
    x = input_list_int()
    x.sort()
    g = x[1] - x[0]
    for i in range(n - 1):
        v1 = x[i]
        v2 = x[i + 1]
        t = v2 - v1
        g = math.gcd(g, t)
    p('YES' if (k - x[0]) % g == 0 else 'NO')
query_count = 1
query_count = input_int()
while query_count:
    query_count -= 1
    solve()
for ans_line in ans:
    print(ans_line)

Solution (Python):
def gcd(a, b):
    if a >= b:
        while a % b != 0:
            (a, b) = (b, a % b)
        return b
    else:
        return gcd(b, a)
n = int(input())
ans = []
for i in range(n):
    (a, b) = (int(num) for num in input().split())
    numlist = [int(num) for num in input().split()]
    g = numlist[1] - numlist[0]
    for j in range(1, a):
        g = gcd(g, numlist[j] - numlist[j - 1])
    if (b - numlist[0]) % g == 0:
        ans.append('YES')
    else:
        ans.append('NO')
for i in ans:
    print(i)