Split Plus K (Codeforces 1909D)
Tags: Greedy, number theory

eliteLAQ - Desert Ruins⠀There are $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ on a blackboard. You are also given a positive integer $$$k$$$. You can perform the following operation some (possibly $$$0$$$) times:  choose a number $$$x$$$ on the blackboard;  erase one occurrence of $$$x$$$;  write two positive integers $$$y$$$, $$$z$$$ such that $$$y+z = x+k$$$ on the blackboard. Is it possible to make all the numbers on the blackboard equal? If yes, what is the minimum number of operations you need?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^{12}$$$) — the number of integers initially on the blackboard and the constant $$$k$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — the initial state of the blackboard.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing an integer: the minimum number of operations you need to make all the numbers on the blackboard equal, or $$$-1$$$ if it is impossible.

Note: In the first test case, $$$k = 1$$$. You can make all the numbers on the blackboard equal to $$$2$$$ with the following operations:   Erase $$$x = 4$$$ and write $$$(y, z) = (2, 3)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains the multiset $$$\{3, 2, 3\}$$$.  Erase $$$x = 3$$$ and write $$$(y, z) = (2, 2)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{2, 2, 2, 3\}$$$.  Erase $$$x = 3$$$ and write $$$(y, z) = (2, 2)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{2, 2, 2, 2, 2\}$$$. This makes all the numbers equal in $$$3$$$ operations. It can be shown that you cannot make all the numbers equal in less than $$$3$$$ operations.In the second test case, $$$k = 3$$$. You can make all the numbers on the blackboard equal to $$$7$$$ with the following operation:   Erase $$$x = 11$$$ and write $$$(y, z) = (7, 7)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{7, 7, 7\}$$$. In the third test case, $$$k = 10$$$. You can make all the numbers on the blackboard equal to $$$40$$$ with the following operations:   Erase $$$x = 100$$$ and write $$$(y, z) = (70, 40)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{70, 40, 40, 100\}$$$.  Erase $$$x = 70$$$ and write $$$(y, z) = (40, 40)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{40, 40, 40, 40, 100\}$$$.  Erase $$$x = 100$$$ and write $$$(y, z) = (40, 70)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{40, 40, 40, 40, 40, 70\}$$$.  Erase $$$x = 70$$$ and write $$$(y, z) = (40, 40)$$$. Note that $$$y+z=x+k$$$. The blackboard now contains $$$\{40, 40, 40, 40, 40, 40, 40\}$$$. In the fourth and in the fifth test case, you can show that it is impossible to make all the numbers on the blackboard equal.

Sample Inputs:
9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906

Sample Outputs:
3
1
4
-1
-1
0
3119
28999960732
-1

Solution (Python):
import sys
input = sys.stdin.readline
import math

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    a = readList()
    a = [v - k for v in a]
    (mi, ma) = (min(a), max(a))
    if mi * ma > 0:
        a = [abs(v) for v in a]
        g = a[0]
        for v in a:
            g = math.gcd(g, v)
        return sum([v // g - 1 for v in a])
    elif mi == ma:
        return 0
    else:
        return -1
for _ in range(int(input())):
    print(solve())

Solution (Python):
from math import gcd

def main():
    for t in range(int(input())):
        (n, k) = map(int, input().split())
        a = list(map(int, input().split()))
        G = k - a[0]
        po = 0
        ne = 0
        ze = 0
        if G > 0:
            po += 1
        elif G < 0:
            ne += 1
        else:
            ze += 1
        for i in range(1, n):
            if k > a[i]:
                po += 1
            elif k < a[i]:
                ne += 1
            else:
                ze += 1
            G = gcd(G, k - a[i])
        if ze > 0:
            if ze < n:
                print(-1)
            else:
                print(0)
        elif po > 0 and ne > 0:
            print(-1)
        else:
            s = sum(a)
            G = abs(G)
            if ne == 0:
                x = k - G
                print((x * n - s) // (k - x))
            else:
                x = k + G
                print((x * n - s) // (k - x))
main()

Solution (Python):
import math

def num_operations(nums):
    count = 0
    GCD = nums[0]
    for num in nums:
        GCD = math.gcd(GCD, num)
    for num in nums:
        count += abs(num // GCD) - 1
    return count

def solve():
    (n, k) = map(int, input().split())
    nums = list(map(int, input().split()))
    for i in range(n):
        nums[i] -= k
    zeros = 0
    positives = 0
    negatives = 0
    for num in nums:
        if num == 0:
            zeros += 1
        elif num > 0:
            positives += 1
        else:
            negatives += 1
    if zeros == n:
        return 0
    if positives == n or negatives == n:
        return num_operations(nums)
    return -1

def main():
    for _ in range(int(input())):
        print(solve())
if __name__ == '__main__':
    main()