[Daimayuan] 添加括号（C++，数学）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan] 添加括号（C++，数学）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

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

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

输入格式

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

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

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

输出格式

输出 $t$ 行。

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

数据范围

$2 \leq n \leq 10000$ , $1 \leq t \leq 100$ , $1≤a_i≤2^{31}−1$

输入样例

输出样例

Yes
No

解题思路

通过不同的加括号方法，可以发现以下几个规律：

（1）第一个数必定是分子；

（2）第二个数必然是分母；

（3）从第三个数开始，任意数都可以成为分子，且互不影响。

同时，很容易知道：分子越多，分母越少，越容易形成整数。

那么我们的算法实现就很简单了：用其他所有数的乘积去尝试整除第二个数。

最后，AC代码如下：文章来源地址https://www.toymoban.com/news/detail-450847.html

#include <iostream>
using namespace std;

int main() {
	int t, n;
	long long a1, a2, sum;
	bool flag;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		a1 = a2 = -1;
		sum = 1;
		flag = false;
		for (int i = 0; i < n; i++) {
			if (i == 1) {
				cin >> a2;
			}
			else {
				cin >> a1;
				sum *= a1;
			}
			
			if (a2 != -1) {
				sum %= a2;
				if (sum == 0) {
					flag = true;
				}
			}
		}
		if (flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}