【题解】洛谷P2651 添加括号III（gcd 数学）

看到是入门难度结果看了半天也不知道啥做法。。

kkk大神给出了答案，a1肯定在分子上，a2肯定在分母上，如果我们想让这个式子更有可能化成整数，那么a1、a3、a4……an都应该在分子上，所以我们只需要枚举求其与a2的gcd，a2/=gcd(a2,ai)，如果a2化成1了，证明可以约分成功化为整数。否则就不能

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iomanip>
#include<stack>
#include<queue>
#define ll long long
using namespace std;
int t;
int a[10010];
ll gcd(ll a,ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		bool flag=false;
		for(int i=1;i<=n;i++)
		{
			if(i!=2)
			{
				if(a[2]>a[i]) a[2]/=gcd(a[i],a[2]);
				else if(a[2]<=a[i]) a[2]/=gcd(a[2],a[i]);
				if(a[2]==1)
				{
					flag=true;
					break;
				}
			}
		}
		if(flag==true) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}