题解 P5949 【[BOI2000]Division expression】
Great_Influence
2020-01-21 10:54:19
容易发现，第二个数字只可能是分母的一部分。
那么我们能够得到的最优答案只可能是分母为第二个数， 其他所有数字做分子。
容易发现， 当我们用括号将第二个数字和后面所有数字全部括起来的时候， 我们正好可以取到这个最优答案。
那么只要判断这个答案是否合法就行了。
我们用第二个数字依次除掉和其他数字的 $\gcd$ ，然后看看最后这个数字是否变成 $1$ 即可。 $\gcd$ 可以用系统内置的。
时间复杂度 $O(n\log n)$ 。
核心代码:
```cpp
read(n);
read(cr);
static int pc;
if(n == 1) puts("YES");
else
{
read(pc);
pc /= __gcd(pc, cr);
Rep(i, 3, n) read(cr), pc /= __gcd(pc, cr);
puts(pc == 1 ? "YES" : "NO");
}
```