1 条题解

  • 0
    @ 2026-11-15 13:23:22

    题目分析

    30 分

    暴力搜索即可。

    60 分

    显然变换过程中数一定变小,记忆化搜索即可。

    正解

    显然如果 nn 中存在除了 2,3,52,3,5 的其他质因子,必定无解。

    考虑三种变换的实质。

    操作 11:去掉当前数中的 11 个质因子 22。

    操作 22 :将当前数中的质因子 22 增加 11 个,去掉当前数中的 11 个质因子 33。

    操作 33 :将当前数中的质因子 22 增加 22 个,去掉当前数中的 11 个质因子 55。

    那么做法就出来了,一个质因子 22 贡献为 11,质因子 33 贡献为 22,质因子 55 贡献为 33。

    复杂度 O(Tlog⁡n)\mathcal{O}(T\log n)。

    • 1

    信息

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