异想之旅：本人原创博客完全手敲，绝对非搬运，全网不可能有重复；本人无团队，仅为技术爱好者进行分享，所有内容不牵扯广告。本人所有文章仅在CSDN和个人博客（一定是异想之旅域名）发布，除此之外全部是盗文！

---

洛谷 P2651 添加括号III

题目描述

现在给出一个表达式，形如 $a_1/a_2/a_3/.../a_n$。

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

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

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

输入格式

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

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

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

输出格式

输出 $t$ 行。

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

输入输出样例

In 1：

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

Out 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$。

题解

看到这道题我最开始想到的是枚举，但是看看数据范围哪怕只有一组数据也是严重超时的。

所以我们要找特殊情况：希望一个分数是整数，则肯定要让出现在分子上的数字尽可能得多。而在本题中， $a_2$ 是一定出现在分母上的，所以我们让其它数字全部出现在分子上

即本题存在一个“最整情况”，当式子为 $a_1/(a_2/a_3/.../a_n)$ ，即化简后为 $(a_1\times a_3\times ...\times a_n)/a_2$ 时分母最小，分子最大，式子最可能是整数。

换句话说，如果存在其它情况使得式子是整数，则在当前情况下也一定是整数（证明：当前式子可由任意一个式子乘 $(a_i^2\times a_j^2\times ...)$ 得到，其中 $a_i,a_j,...$ 为分母上除了 $a_2$ 外的数）。

接下来就要判断在“最整情况”下式子是否为整数。我们自然可以把 $(a_1\times a_3\times ...\times a_n)/a_2$ 的结果算出来，但这需要高精，而且事实上也没有必要，因此我们优化：

求分母与分子的最大公因数，判断约分后分母是否为 $1$ 。进而地，我们求分母与分子上每一个因数 $a_1,a_3,...,a_n$ 的最大公因数并依次用得到的数去除（除不是除以）分母的 $a_2$ ，看分母是否能变为 $1$ 即可。

#include <bits/stdc++.h>
using namespace std;int n, a[10001];inline void read(int &x) {  // 快读，来自我之前的博客x = 0;short flag = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-') flag = -1;c = getchar();}while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48);c = getchar();}x *= flag;
}int main() {int t;read(t);while (t--) {  // t组数据read(n);for (int i = 1; i <= n; i++) read(a[i]);  // 读入每一个数字a[2] /= __gcd(a[1], a[2]);for (int i = 3; i <= n; i++) {a[2] /= __gcd(a[i], a[2]);  // 不停除以两数的最大公约数if (a[2] == 1) break;  // 如果已经为整数则跳出}// 判断最后分子是否化为1if (a[2] == 1)cout << "Yes\n";elsecout << "No\n";}return 0;
}

__gcd() 是求两个数字最大公因数的内置函数，存在于头文件 algorithm 中，已经允许在CCF系列竞赛中使用。

下面是一个我思考过程中遇到的问题，也没能描述清楚，不理解的跳过吧：

有人会问，分子不去操作，这样子只有分母在减小不会有分子上的数字被重复使用吗？答：不会的，因为我们自始至终没有使用整个分子，而是在使用分子的每一个因数。