洛谷题面

题目大意

有\(N(1\leq N\leq 100)\)个数\(x_1,x_2,..,x_n\)。

可以根据需要多次执行以下操作：选择两个不同的下标 \(i\) 和 \(j\)，保持 \(x_i \gt x_j\) ，然后令 \(x_i \gets x_i - x_j\)。

目标是使所有数字的总和尽可能小。

请找到这个最小的总和。

题目分析

\(\boxed{\texttt{性质1：最优解中，所有数都一定会被修改成相等的数。}}\)

证明：

考虑反证法。

假设最优解中并非所有数都相等，那么我们通过相减一定可以得到更优解，这与最优解的定义矛盾，所以得证。

\(\boxed{\texttt{性质2：每次操作后，所有数组的 gcd 保持不变。}}\)

证明：

考虑 \(a_i,a_{j}(a_i>a_{j})\)，令 \(a=\gcd(a_i,a_{j})\)。

所以 \(a_i=ak,a_j=ap\)\((k,p\) \(\texttt{均为正整数且}\)\(k>p)\)。

\(a_i-a_j\)

\(=ak-ap\)

\(=a(k-p)\)

\(\because\) \((k-p)\) 为正整数。

\(\therefore\) 得证。

所以答案为 \(\gcd(a_1,a_2,\cdots,a_{n-1},a_n)\times n\)。

代码

//2021/11/17

#define _CRT_SECURE_NO_WARNINGS

#include 

#include 

#include //need "INT_MAX","INT_MIN"

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

int n;

inline int gcd(int a,int b)
{
	if(b==0)
	{
		return a;
	}
	
	return gcd(b,a%b);
}

int main(void)
{
	n=read();
	
	int ans(0);
	
	for(register int i=1;i<=n;i++)
	{
		int x=read();
		
		ans=gcd(ans,x);
	}
	
	printf("%d\n",ans*n);
	
	return 0;
}