添加括号III

题意

给出连续除法 a1/a2/.../an，可以任意添加括号，问能否使结果成为整数。

思路

通过括号 a1/(a2/a3/a4/...)，a3..an 都有机会进入总分子。因此可行的充要条件是：a2 的全部质因子幂能由 a1*a3*...*an 约掉。

不直接计算巨大乘积。先令：

text

1denominator=a2/gcd(a1,a2)

再依次用每个后续数与当前分母的 gcd 约分。最后分母等于 1 则输出 Yes。

Python 知识

math.gcd 让约分直接作用于剩余分母。
列表切片取得每组表达式，读取指针处理变长测试用例。
逐步约分避免构造可能极大的乘积，虽然 Python 支持大整数，也应控制不必要运算。
条件表达式生成 Yes/No。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：大整数不代表应忽略算法规模。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：变长多组输入。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys
from math import gcd


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    test_count = data[0]
    pos = 1
    answer = []

    for _ in range(test_count):
        n = data[pos]
        numbers = data[pos + 1:pos + n + 1]
        pos += n + 1
        denominator = numbers[1] // gcd(numbers[0], numbers[1])
        for factor in numbers[2:]:
            denominator //= gcd(denominator, factor)
        answer.append("Yes" if denominator == 1 else "No")

    print("\n".join(answer))


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
 * P2651 添加括号III
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int a[10005];
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        // a1 / a2 / a3 / ... / an → 通过加括号可以使 a2 成为分母
        // 判断 a1 * a3 * ... * an 是否能被 a2 整除
        // 即 a2 / gcd(a1,a2) 继续除以 gcd(..., ai) 最终是否为 1
        int den = a[2];
        den /= __gcd(a[1], den); // a1 可以约分
        for (int i = 3; i <= n; ++i) {
            den /= __gcd(den, a[i]);
            if (den == 1) break;
        }
        puts(den == 1 ? "Yes" : "No");
    }
    return 0;
}

复杂度

每个数参与一次 gcd，总时间复杂度 $O(n\log V)$ ，额外空间为当前测试用例切片 $O(n)$ 。

总结

括号结构看似很多，但能否为整数只取决于第二项分母能否被其它项完全约掉。

目录

题意

思路

Python 知识

代码

复杂度

总结