P2651. 添加括号III

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 187 阅读时长 ≈ 1 分钟

考点

  • 最大公约数

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int t, n, a, b, x, g;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {
  cin >> t;
  while (t--) {
    cin >> n >> a >> b, n -= 2, b = b / gcd(a, b);
    while (n--) {
      cin >> x;
      b = b / gcd(x, b);
    }
    b == 1 ? cout << "Yes" << endl : cout << "No" << endl;
  }
  return 0;
}

思路

这道题第一个坑点，就是没告诉你括号是可以嵌套的

比如这个式子\(1/\left( \left( 2/3 \right) /4 \right)\)，除了第二位必须是分母，其余都可以变成分子

第二个坑点，测试点会卡你不准用乘法，否则long long都溢出

由于只需要保证分母为1，所以每次只保存分母除去与分子的最大公约数即可