Codeforces 1113B. Sasha and Magnetic Machines 题解

题目链接：Codeforces 1113B. Sasha and Magnetic Machines
题目大意：给你一个长度为\(n\)的数列，你只能进行一次操作，操作为：选择两个数\(a_i,a_j\)，\((1 \leq i,j \leq n)\)，再选一个数\(x(x\mid a_i)\)，然后\(a_i=\frac{a_i}{x},a_j=a_j\times x\)。
题解：上面加粗的字很重要，否则就是用堆+贪心了，我们肯定是给最小的乘，所以只要枚举除数与被除数就可以了。

#include <cstdio>
#define Maxn 50000
int a[Maxn+5];
int minn(int a,int b){
	return a<b?a:b;
}
int main(){
	int n;
	scanf("%d",&n);
	int ans=0;
	int mn=(1<<30);
	int sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]<mn){
			mn=a[i];
		}
		sum+=a[i];
	}
	ans=sum;
	int now;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i];j++){
			if(a[i]%j!=0){
				continue;
			}
			now=sum-mn-a[i];
			ans=minn(ans,now+mn*j+a[i]/j);
		}
	}
	printf("%d\n",ans);
	return 0;
}