P2651 添加括号III

这道题其实很简单，我们只需要变行就可以啦.

a1一定是分子，a2一定是分母 a1 /(a2/a3/a4/a5…an)

化简可以得到a1a3a4a5an/a2

我们只需要用 a1 a3 …an分别与a2求最大公约数gd 看看有没有那一次可以使得 a2/gd = =1
如果某个ai(i= 1 3 4 5 6 … n)与a2的最大公约数是 gd 并且 a2/gd==1，那么可以断定,可以得到整数，即输出Yes，否则输出No

下面是 AC代码~

#include <iostream>
using namespace std;
#define Max 100000
int a[Max];
int gcd(int a,int b);
bool fun(int a[],int t);
    int main()
    {
        int n,t;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>t;
            for(int j=1;j<=t;j++)
            {
                cin>>a[j];
            }
            if(fun(a,t))
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        return 0;
    }

    bool fun(int a[],int t)
    {
        if(t==1)
        {
            return true;
        }
        int gd=gcd(a[1],a[2]);
        a[2]/=gd;
        if(a[2]==1)
        {
            return true;
        }

        for(int i=3;i<=t;i++)
        {
            gd=gcd(a[i],a[2]);
            a[2]/=gd;
            if(a[2]==1)
            {
                return true;
            }
        }
        return false;
    }

    int gcd(int a,int b)
    {
        return a%b==0? b:gcd(b,a%b);
    }