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.

有n把剑，每把剑的类型为x个，有一天y个人闯进来，并且每把类型的剑都拿走了z个，a[i]表示第i种类型的剑剩余a[i]个，你不知道x,y,z，求最小的y值

思路

因为我们不知道 x , y , z x,y,z x,y,z，要想 y y y的值最小，我们可以假定 x x x为 a [ i ] a[i] a[i]中的最大值，这样问题就变成了求最大的 z z z值。这时我们可以求出所有 x − a [ i ] x-a[i] x−a[i]的和，因为最后 a [ i ] + y ′ ∗ z a[i]+y'*z a[i]+y′∗z的值要等于 x x x，所以我们还需要求出 t = g c d ( t , a [ i ] ) ( a [ i ] ! = x ) t=gcd(t,a[i]) (a[i]!=x) t=gcd(t,a[i])(a[i]!=x)作为因子的最大值，然后求出 s u m sum sum的所有因子，找出 s u m sum sum能够整除的最大 z z z即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
ll a[N];
void solve(){
    int n;cin>>n;
    rep(i,0,n) cin>>a[i];
    sort(a,a+n);
    ll sum=0,ba=a[n-1],t=0;
    rep(i,0,n){
        if(a[i]!=ba){
            sum+=ba-a[i];
            t=__gcd(t,ba-a[i]);
        }
    }
    ll fac=0;
    rep(i,1,sum/i+1){
        if(sum%i==0){
            if(i<=t) fac=max(fac,i);
            if(sum/i<=t) fac=max(fac,sum/i);
        }
    }
    cout<<sum/fac<<' '<<fac<<endl;
}
int main(){
    IOS;
    //int t;cin>>t;
    //while(t--){
        solve();
    //}
    return 0;
}