【代码源】每日一题 添加括号

2022.05.06

题目链接：添加括号 - 题目 - Daimayuan Online Judge

题目描述：

现在给出一个表达式，形如 a1/a2/a3/.../an。

如果直接计算，就是一个个除过去，比如 1/2/1/4=1/8。

然而小 A 看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 (1/2)/(1/4)=2。

现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

输入格式

一个测试点中会有多个表达式。

第一行 t ，表示表达式数量。

对于每个表达式，第一行是 n，第二行 n 个数，第 i 个数表示 ai

输出格式

输出 tt 行。

对于每个表达式，如果可以通过添加括号改变顺序使其变成整数，那么输出 Yes，否则输出 No。

数据范围

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

输入样例

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

输出样例

Yes
No

思路：

a1/a2/a3/.../an最后化成分子/分母的形式，那么为使它的值为整数，肯定分母越少越好（贪心）。而a2肯定在分母上，因为它不可能变换到分子上去。a3……an都可以通过添加括号的方式变换到分子上（ 例：a1/( ( (a2/a3)/a4 )/a5 ) ）

所以，只需求a1*a3*.....*an能否被a2整除，即能否通过a1,a3,,,,an把a2除尽。

详见代码：

#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]); //除掉最大公因数
        }
        if (now == 1) // a2被除尽
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}