Swords (Codeforces 1216D)
Tags: Math, math

There were $$$n$$$ types of swords in the theater basement which had been used during the plays. Moreover there were exactly $$$x$$$ swords of each type. $$$y$$$ people have broken into the theater basement and each of them has taken exactly $$$z$$$ swords of some single type. Note that different people might have taken different types of swords. Note that the values $$$x, y$$$ and $$$z$$$ are unknown for you.The next morning the director of the theater discovers the loss. He counts all swords — exactly $$$a_i$$$ swords of the $$$i$$$-th type are left untouched.The director has no clue about the initial number of swords of each type in the basement, the number of people who have broken into the basement and how many swords each of them have taken.For example, if $$$n=3$$$, $$$a = [3, 12, 6]$$$ then one of the possible situations is $$$x=12$$$, $$$y=5$$$ and $$$z=3$$$. Then the first three people took swords of the first type and the other two people took swords of the third type. Note that you don't know values $$$x, y$$$ and $$$z$$$ beforehand but know values of $$$n$$$ and $$$a$$$.Thus he seeks for your help. Determine the minimum number of people $$$y$$$, which could have broken into the theater basement, and the number of swords $$$z$$$ each of them has taken.

Input: The first line of the input contains one integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^{5})$$$ — the number of types of swords.The second line of the input contains the sequence $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^{9})$$$, where $$$a_i$$$ equals to the number of swords of the $$$i$$$-th type, which have remained in the basement after the theft. It is guaranteed that there exists at least one such pair of indices $$$(j, k)$$$ that $$$a_j \neq a_k$$$.

Output: Print two integers $$$y$$$ and $$$z$$$ — the minimum number of people which could have broken into the basement and the number of swords each of them has taken.

Note: In the first example the minimum value of $$$y$$$ equals to $$$5$$$, i.e. the minimum number of people who could have broken into the basement, is $$$5$$$. Each of them has taken $$$3$$$ swords: three of them have taken $$$3$$$ swords of the first type, and two others have taken $$$3$$$ swords of the third type.In the second example the minimum value of $$$y$$$ is $$$1$$$, i.e. the minimum number of people who could have broken into the basement, equals to $$$1$$$. He has taken $$$7$$$ swords of the first type.

Sample Inputs:
3
3 12 6

2
2 9

7
2 1000000000 4 6 8 4 2

6
13 52 0 13 26 52

Sample Outputs:
5 3

1 7

2999999987 2

12 13

Solution (Python):
import math
import random
import sys

class FastIO:

    def __init__(self):
        self.random_seed = random.randint(0, 10 ** 9 + 7)
        return

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().strip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().strip())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().strip().split()))

    @staticmethod
    def read_str():
        return sys.stdin.readline().strip()

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().strip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().strip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def ceil(a, b):
        return a // b + int(a % b != 0)

    def hash_num(self, x):
        return x ^ self.random_seed

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

    def inter_ask(self, lst):
        self.st(lst)
        sys.stdout.flush()
        res = self.read_int()
        return res

    def inter_out(self, lst):
        self.st(lst)
        sys.stdout.flush()
        return

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        n = ac.read_int()
        nums = ac.read_list_ints()
        x = max(nums)
        rest = n * x - sum(nums)
        z = x - nums[0]
        for num in nums[1:]:
            z = math.gcd(x - num, z)
        ac.lst([rest // z, z])
        return
Solution().main()

Solution (Python):
from math import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
b = max(a)
c = [b - i for i in a]
d = reduce(gcd, c)
e = sum(c) // d
print(e, d)

Solution (Python):
from math import gcd

def anime():
    n = int(input())
    a = list(map(int, input().split()))
    x = max(a)
    b = [x - ai for ai in a]
    z = b[0]
    for bi in b:
        if bi != 0:
            z = gcd(z, bi)
    y = sum((bi // z for bi in b))
    print(y, z)
if __name__ == '__main__':
    t = 1
    for _ in range(t):
        anime()