欧几里得&&唯一分解入门题

题目描述：

给出$n$个正整数X1,X2,X3...XnX_1,X_2,X_3...X_nX1​,X2​,X3​...Xn​,判断表达式X1/X2/X3/.../XnX_1/X_2/X_3/.../X_nX1​/X2​/X3​/.../Xn​是否可以通过添加括号使得结果为整数。

分析：

设表达式结果为$E(x)$,那么一定存在$E(x)=A/B$，观察式子发现，X2X_2X2​必然位于分母，此处可使用贪心的思想：使得表达式是整数则分母越少越好。
于是只需判断E(x)=X1∗X3∗...∗Xn/X2E(x)=X_1*X_3*...*X_n/X_2E(x)=X1​∗X3​∗...∗Xn​/X2​是否为整数，循环每个数与X2X_2X2​约分即可

std：

#include<cstdio>
using namespace std;
int GCD(int x,int y)
{
	if(y==0)return x;
	return GCD(y,x%y);
}
int a[1005];
int main()
{
	int n;
	scanf("%d",&n);
	scanf("%d",&a[1]);
	int ans=a[1];
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&a[i]);
		ans=ans/a[i];
	}
	printf("%d\n",ans);
	int tmp=GCD(a[1],a[2]);
	a[2]=a[2]/tmp;
	for(int i=3;i<=n;i++)
	{
		if(a[2]==1)
		{
			printf("YES\n");
			return 0;
		}
		int g=GCD(a[i],a[2]);
		a[2]=a[2]/g;
	}
	printf("NO\n");
}