1 条题解

  • 0
    @ 2026-11-15 13:33:24

    题目分析

    20 分

    暴力枚举三元组即可。

    40 分

    注意到如果确定 i,ji,j,那么 bb 就确定了,就可以确定 aka_k 的值,于是只需要枚举 i,ji,j 即可。

    时间复杂度 O(n2)\mathcal{O}(n^2)。

    60 分

    注意到 nn 其实并不重要,相同的数是可以放到一起的。

    80 分

    考虑枚举 aja_j 的值,那么 aia_i 一定是其因子,于是根号枚举即可,时间复杂度 O(nV)\mathcal{O}(n\sqrt{V}),VV 是值域。

    正解

    考虑根号分治,对于 ai≤V23a_i\le V^{\frac{2}{3}} 的时候根号暴力枚举,否则可以注意到 $b\le \lfloor \frac{V}{a_i} \rfloor \le V^{\frac{1}{3}}$,此时枚举 bb 即可。

    综上时间复杂度 O(nV13)\mathcal{O}(nV^{\frac{1}{3}})。

    • 1

    信息

    ID
    66
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者