题目链接：D. Swords

题目

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 ai 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.

输入

The first line of the input contains one integer n (2≤n≤2⋅10^5) — the number of types of swords.

The second line of the input contains the sequence a1,a2,…,an (0≤ai≤10^9), where ai 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 aj≠ak.

输出

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.

样例

input

3
3 12 6

output

5 3

input

2
2 9

output

1 7

input

7
2 1000000000 4 6 8 4 2

output

2999999987 2

input

6
13 52 0 13 26 52

output

12 13

题意

有 n 种🗡，一开始这些🗡的数量是一样的，后来来了一群人拿走了一些🗡。注意：

1. 每个人只能拿走一种🗡
2. 每个人拿走的🗡的数量是相同的

题中会给你这些人拿完以后每种🗡剩下的数量，问你 最少 有多少人拿🗡，每人拿走了多少🗡。

解题思路

先把这些数都存起来，找到最大的数，然后假装数量最多的就是初始的数量，用这个数减去每一个其他的 ai ，加起来以后获得了总共拿走了多少🗡。在获得每一个缺少的数量的时候获取所有被拿走的剑的最大公约数，可能有点恍惚，我举个例子：

比如第一个样例是 3, 12, 6 那么假设的被拿走的🗡的数量就是 9, 0, 6 总共是 15
9, 0, 6 的最大公约数就是 3 【 0 直接忽略
所以 3 就是拿走单位，就是说每个人拿走的数量就是这个最大公约数 3 ，最少的人数自然就是：
被拿走的总数/每种被拿走的数量的最大公约数 = 15/3 = 5(人)

这个题着实难倒我了一下下，主要是一开始题意理解错了。这里猹温馨提示大家，英文题少用翻译，真到比赛的时候看不懂就真崩了。

代码

#include <iostream>
#include <set>

typedef long long ll;

using namespace std;

struct hon_cmp {bool operator () (const ll &a, const ll &b) {return a > b;}};

void EX(ll &a, ll &b) {ll t = a; a = b; b = t;}

ll BCD(ll a, ll b) {
        if (!a) return b;
        if (!b) return a;
        if (a < b) EX(a, b);
        while (b) {ll t = a % b; a = b; b = t;}
        return a;
}

int main() {
        ios::sync_with_stdio(0); cin.tie(0);
        ll t; cin >> t;
        ll n = t;
        multiset<ll, hon_cmp> v;
        while (t--) {
                ll a; cin >> a;
                v.insert(a);
        }
        ll m = *v.begin(), s = 0, p = 0;
        for (ll a : v) {
                ll b = m - a;
                p = BCD(p, b);
                s += b;
        }
        cout << s/p << ' ' << p << endl;
        return 0;
}