CodeForces-1216D Swords

传送门：CodeForces - 1216D

题目描述

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 $a_1,a_2,…,a_n$ $(0≤a_i≤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 $a_j≠a_k$.

输出描述

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.

题意分析

n把剑，其中有一种剑没被偷过（就是最大值），其余都被偷过，每个人偷的数目都相同，应该就是gcd！

样例输入

3
3 12 6

样例输出

5 3

AC代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

ll a[200002];

int main() {
    IOS;
    int n;
    cin>>n;
    int i;
    ll t=-1,sum=0;
    for(i=0; i<n; i++) {
        cin>>a[i];
        sum+=a[i];
        t=max(t,a[i]);
    }
    ll f=0;
    for(i=0;i<n;i++){
        f=__gcd(f,t-a[i]);
    }
    ll p;
    p=(t*n-sum)/f;
    cout<<p<<" "<<f<<endl;
}