洛谷p2651 添加括号III （最大公约数gcd）

题目分析

题目难度：普及-
题目的问题是：添加一系列括号之后是否可以使得a1/a2/a3/a4/……/an是整数。
添加括号的的方法是任意的，所以不能暴力的去想如何填括号，应从更深层次的角度来考虑最普遍解，首先a1一定在分子上，a2一定在分母上，那么可以通过添加一系列的括号，使得a3 a4……an都放在分子上即a1/（a2/a3/a4/……/an）。
这是一种类似于贪心的想法，如果将所有能放到分子上的数都放到分子上之后，该分数仍然不能为整数，那么一定就是输出“No”了；反之，如果能为整数，那么一定存在至少一个放括号的方式使得该分数为整数，就可以输出"Yes"了。

AC代码

//Author:snnu_lgw
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//目的是判断添加括号后能否使得结果为整数
//故a1/a2/a3/a4/……/an
//不论括号如何添加，a1一定为分子，a2一定为分母，那么将后续所有整数都放到分子上 
int gcd(int a,int b)
{
	while(b)
	{
		int mod = a%b;
		a = b;
		b = mod;
	}
	return a;	
} 
int a[10000+100];
int main()
{
	int n,t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		int mod = gcd(a[1],a[2]);
		a[2]/=mod;
		for(int i=3;i<=n;i++)
		{
			mod = gcd(a[2],a[i]);
			a[2]/=mod;
			if(a[2]==1) break;
		}
		if(a[2]==1) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}	 
	return 0;
}