洛谷-P2651 添加括号III

洛谷-P2651 添加括号III

原题链接：https://www.luogu.com.cn/problem/P2651

• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 说明/提示
• C++代码

---

题目描述

现在给出一个表达式，形如 (a_{1}/a_{2}/a_{3}/.../a_{n})。

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

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

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

输入格式

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

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

对于每个表达式，第一行是 (n)，第二行 (n) 个数，第 (i) 个数表示 (a_{i})。

输出格式

输出 (t) 行。

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

输入输出样例

输入 #1

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

输出 #1

Yes
No

说明/提示

• 对于 (40\%) 的数据，(n le 16)。
• 对于 (70\%) 的数据，(n le 100)。
• 对于 (100\%) 的数据， (2 le n le 10000)，(1 le t le 100)，(1 le a_{i}le 2^{31}-1)。

C++代码

#include <iostream>
#include <algorithm>
using namespace std;

int t, n, a[10005];

int main() {
    cin >> t;
    for (int i=0; i<t; ++i) {
        cin >> n;
        for (int j=0; j<n; ++j)
            cin >> a[j];
        a[1] /= __gcd(a[0], a[1]);
        for (int j=2; j<n && a[1]!=1; ++j)
            a[1] /= __gcd(a[j], a[1]);
        if (a[1] == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}