Nezzar and Board (Codeforces 1477A)
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 sys, io, os, math
from math import ceil, log, gcd, sqrt
from itertools import permutations
import operator
mod = 1000000007
mod1 = 998244353

def intinp():
    return int(sys.stdin.readline())

def strinp():
    return sys.stdin.readline()

def arrinp():
    return list(map(int, sys.stdin.readline().strip().split()))

def mulinp():
    return map(int, sys.stdin.readline().strip().split())

def flush():
    return stdout.flush()

def power_two(x):
    return 1 << x

def lcm(a, b):
    return a * b // gcd(a, b)

def solve():
    (n, k) = mulinp()
    t = arrinp()
    res = 0
    t.sort()
    for i in range(1, n):
        res = gcd(res, t[i] - t[0])
    if (k - t[0]) % res:
        print('NO')
        return
    print('YES')

def main():
    tc = intinp()
    while tc:
        solve()
        tc -= 1
main()

Solution (Python):
import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True

def SieveOfEratosthenes(n):
    prime = []
    primes = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if primes[p] == True:
            prime.append(p)
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return prime

def primefactors(n):
    fac = []
    while n % 2 == 0:
        fac.append(2)
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 2):
        while n % i == 0:
            fac.append(i)
            n = n // i
    if n > 1:
        fac.append(n)
    return fac

def factors(n):
    fac = set()
    fac.add(1)
    fac.add(n)
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            fac.add(i)
            fac.add(n // i)
    return list(fac)
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    g = 0
    for i in range(1, len(a)):
        g = math.gcd(g, a[i] - a[0])
    if (k - a[0]) % g == 0:
        print('YES')
    else:
        print('NO')

Solution (Python):
import math

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

def solve():
    (n, k) = map(int, input().split())
    xs = list(map(int, input().split()))
    xs.sort()
    k -= xs[0]
    for i in range(1, n):
        xs[i] -= xs[0]
    xs[0] = 0
    gcd = 0
    for i in range(n):
        gcd = math.gcd(gcd, xs[i])
    if k % gcd == 0:
        return print('YES')
    print('NO')
main()