题解 P5949 【[BOI2000]Division expression】

2020-01-21 10:54:19


容易发现,第二个数字只可能是分母的一部分。

那么我们能够得到的最优答案只可能是分母为第二个数, 其他所有数字做分子。

容易发现, 当我们用括号将第二个数字和后面所有数字全部括起来的时候, 我们正好可以取到这个最优答案。

那么只要判断这个答案是否合法就行了。

我们用第二个数字依次除掉和其他数字的 $\gcd$ ,然后看看最后这个数字是否变成 $1$ 即可。 $\gcd$ 可以用系统内置的。

时间复杂度 $O(n\log n)$ 。

核心代码:

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");
}