题解 CF1216D 【Swords】

Bertha 。 2023-06-01 12:42 11阅读 0赞

大水题，感觉比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)$

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

emm...（通过看样例）易得，$z\_\{max\}=gcd(b\[i\]|b\[i\]!=0,1≤i≤n)$（下文称$b\_\{gcd\}$），$y=\\sum\\limits\_\{i=1\}^\{n\}\{c\_i\}$

--------------------

证明：

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

①$x=max(a\[i\]|1≤i≤n)$

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

②$x>max(a\[i\]|1≤i≤n)$

此时$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;
    }

转载于:https://www.cnblogs.com/wyzwyz/p/11565230.html