题解 CF1216D 【Swords】

大水题，感觉比C题水多了。。。（证明倒是挺难）

题目大意：额，这个（实在总结不出）

还是题目描述吧：仓库里有$n$种相同数量（$x$把）的剑（但你不知道有多少），一天有$y$人闯进了仓库，每人拿了$z$把相同的剑（每个人拿的种类不一定相同），现在给你每把剑所剩下的数量$a_i$，求最小的$y$，并求出$z$

令$a_{max}=max(a[i]|1≤i≤n)$

令$b[i]=a_{max}-a[i](1≤i≤n)$

令$b_{gcd}=gcd(b[i]|b[i]!=0,1≤i≤n)$

令$c[i]=\frac{b[i]}{b_{gcd}}(1≤i≤n)$

emm...（通过看样例）易得，$z_{max}=b_{gcd}$，$y=\sum\limits_{i=1}^{n}{c_i}$

证明：

反证法。设存在比$b_{gcd}$更大的$z$值，令$Max$等于这个$z$值

①$x=a_{max}$

此时$Max$应能整除所有非0的$b[i]$且比$b_{gcd}$大，不符合$gcd$的定义（最大公约数），矛盾

②$x>a_{max}$

此时$Max$应能整除所有非0的$b[i]+x-a_{max}$，此时若$x-a_{max}≤b_{gcd}$，那么$Max$肯定小于等于$b_{gcd}$，矛盾

故仅需考虑$x-a_{max}>b_{gcd}$这种情况。此时$Max=gcd(b[i]+x-a_{max}|1≤i≤n)$

根据$gcd$的定义，可以证明：若多个数都加上一个值后$gcd$更大，只能是加上了它们的公约数的倍数。（这里不再赘述，读者自证不难）

根据我们此题得到：$b[i](1≤i≤n)$中至少有一个为$0$，故$gcd(b[i](1≤i≤n))=0$

故$gcd(b[i]+d(1≤i≤n,d∈N^+))≤b_{gcd}$

故得，$Max≤b_{gcd}$，矛盾

故$z_{max}=b_{gcd}$，证毕

注意特判$b_{gcd}$为$0$的情况，还有，提示一下： 要开$long$ $long$！

代码如下：

#include<cstdio>

#define ll long long

inline ll read(){

	ll r=0,f=1;

	char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();

	return r*f;

}

ll n,a[200002],Max,Min=1e9+10,y,z;

ll gcd(ll a,ll b){

	return b?gcd(b,a%b):a;

}

inline ll max(ll a,ll b){

	return a>b?a:b;

}

inline ll min(ll a,ll b){

	return a<b?a:b;

}

int main(){

	n=(int)read();

	for(int i=1;i<=n;i++){

		a[i]=read();

		Max=max(Max,a[i]);

		Min=min(Min,a[i]);

	}

	z=Max-Min;

	for(int i=1;i<=n;i++){

		if(Max==a[i])continue;

		z=gcd(z,Max-a[i]);

	}

	if(!z){

		printf("0 0");

		return 0;

	}

	for(int i=1;i<=n;i++)y+=(Max-a[i])/z;

	printf("%lld %lld",y,z);

	return 0;

}