[code source] add brackets to the daily question

2022.05.06

Topic link ： Add brackets - subject - Daimayuan Online Judge

Title Description ：

Now give an expression , Form like  a1/a2/a3/.../an.

If you calculate directly , Is to divide the past one by one , such as  1/2/1/4=1/8.

But little  A  It's uncomfortable to see a score , I want to make it an integer by adding some parentheses . One possible way is  (1/2)/(1/4)=2.

Now give this expression , Ask whether you can change the operation order by adding some parentheses to make it an integer .

Input format

There will be multiple expressions in a test point .

first line  t , Represents the number of expressions .

For each expression , The first line is  n, The second line  n  Number , The first  i  The number means  ai

Output format

Output  tt  That's ok .

For each expression , If you can change the order by adding parentheses to make it an integer , Then output  Yes, Otherwise output  No.

Data range

2≤n≤10000,1≤t≤100,1≤ai≤2^31−1

sample input

2
4
1 2 1 4
5
6 5 7 9 12

sample output

Yes
No

Ideas ：

a1/a2/a3/.../an Finally, it turns into molecules / The form of denominator , So to make its value an integer , The less the denominator, the better （ greedy ）. and a2 It must be on the denominator , Because it can't be transformed into molecules .a3……an Can be transformed to molecules by adding parentheses （ example ：a1/( ( (a2/a3)/a4 )/a5 ) ）

therefore , Demand only a1*a3*.....*an Can be a2 to be divisible by , That is, whether it can pass a1,a3,,,,an hold a2 Divide up .

See the code for details. ：

#include <bits/stdc++.h>
using namespace std;
int a[10009];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int now = a[2];
        for (int i = 1; i <= n; i++)
        {
            if (i == 2)
                continue;
            now = now / __gcd(now, a[i]); // Remove the greatest common factor 
        }
        if (now == 1) // a2 Be eliminated 
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}