Row GCD (Codeforces 1458A)
Tags: Math, number theory

You are given two positive integer sequences $$$a_1, \ldots, a_n$$$ and $$$b_1, \ldots, b_m$$$. For each $$$j = 1, \ldots, m$$$ find the greatest common divisor of $$$a_1 + b_j, \ldots, a_n + b_j$$$.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{18})$$$.The third line contains $$$m$$$ integers $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_j \leq 10^{18})$$$.

Output: Print $$$m$$$ integers. The $$$j$$$-th of them should be equal to GCD$$$(a_1 + b_j, \ldots, a_n + b_j)$$$.


Sample Inputs:
4 4
1 25 121 169
1 2 7 23

Sample Outputs:
2 3 8 24

Solution (Python):
import math
import random
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)

def solve():
    (n, m) = LI()
    a = LI()
    b = LI()
    if n == 1:
        return ' '.join([str(b[i] + a[0]) for i in range(m)])
    cgcd = a[1] - a[0]
    for i in range(2, n):
        cgcd = math.gcd(cgcd, a[i] - a[0])
    return ' '.join([str(math.gcd(cgcd, a[0] + b[i])) for i in range(m)])

def main():
    for _ in range(1):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
import math, sys
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
if n == 1:
    print(' '.join([str(a[0] + i) for i in b]))
    sys.exit()
di = [abs(a[i] - a[i - 1]) for i in range(1, len(a))]
d = abs(di[0])
for i in di:
    d = abs(math.gcd(d, i))
print(' '.join([str(math.gcd(d, a[0] + i)) for i in b]))

Solution (Python):
import math
(t, a, g) = (input(), list(map(int, input().split())), 0)
for v in a[1:]:
    g = math.gcd(g, v - a[0])
print(*[math.gcd(g, v + a[0]) for v in map(int, input().split())])