1 条题解

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

    题目分析

    30 分

    显然每个位置最多操作一次,于是暴力枚举即可,时间复杂度 O(2n)\mathcal{O}(2^n)。

    60 分

    无脑 dp 即可,显然在最优解(假设最初所有数的 gcd⁡≠1\gcd \ne 1 )中至少有一个位置是操作了的,于是枚举该位置然后在值域上 dp 即可。

    正解

    多想一想可以发现答案一定不超过 33。

    因为 gcd⁡(n−1,n)=1\gcd(n-1,n)=1,所以最坏情况就是把位置 n−1n-1 和 nn 都操作一遍。

    那么就好做了,先检查能不能不操作,再检查能否只操作位置 n−1n-1 或位置 nn,都不行就输出 33。

    • 1

    信息

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