洛谷p2651 添加括号III (最大公约数gcd)

  • 2022-07-16 10:59:32

洛谷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;
}

猜你喜欢