Luogu P2651 添加括号III

Luogu P2651 添加括号III

解析

• $ a_1 $ 肯定是分子，$ a_2 $ 肯定是分母，那么尽可能多的是 $ a_3 $ 以后的变为分子
• $ a_1 / ( a_2 / a_3 / a_4 / ... ) = a_1 a_3 a_4 ... / a_2 $，所以我们只要确认 $ a_1 a_3 a_4 ... / a_2 $ 是否是整数
• 进行约分，若 $ a_2 $ 能被约分成 $ 1 $，那么就是整数；只需每次将 $ a_2 = a_2 / gcd ( a_2 , a_i ) , i = ( 1 , 3 , 4 , 5 ... ) $

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int t,n,s[10005];
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&s[i]);
        for(int i=3;i<=n;i++) s[2]/=gcd(s[2],s[i]);
        s[2]/=gcd(s[2],s[1]);
        if(s[2]==1) puts("Yes");
        else puts("No");
    }
    return 0;
}