1 条题解

  • 0
    @ 2026-11-15 17:07:43

    题目分析

    首先,我们考虑:数列 bb 一定严格单调递减。

    为什么呢?模了一个数 CC 后,所得的 A′A' 一定小于 CC,接下来再用一个 D>CD>C,发现 A′ mod D=A′A'\bmod D=A',没有任何意义。

    因此,先将 aa 从大到小排序。

    而 n≤20n\le20,我们可以用二进制枚举。

    即,用一个 nn 位的二进制数,若第 ii 位为 11,则表示选中 aia_i;否则表示不选中。

    时间复杂度 O(nlog⁡n+n⋅2n)O(n\log n+n\cdot 2^n)。

    当然 dfs 也是可行的。

    以下代码均为单测。

    • 1

    信息

    ID
    146
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者