1 条题解

  • 0
    @ 2026-11-15 22:53:17

    T4 数学家猫猫

    • 首先注意到,操作中的 min⁡\min 相当于直接删除较大的数,不影响较小的数;而 gcd⁡\gcd 操作得到的新数一定不大于原来两个数的最小值。因此,不论如何选择 min⁡\min 或 gcd⁡\gcd,最终留下的数一定等于原数组某个非空子集的 gcd⁡\gcd。
    • 因此,问题转化为:统计原数组所有非空子集的 gcd⁡\gcd,共有多少种不同的值。
    • 具体做法:
      • 对每个 A_iA\_i 分解所有因数。
      • 对每个因数 dd,记录哪些 A_iA\_i 是 dd 的倍数。
      • 枚举每个因数 dd,对所有是 dd 的倍数的 A_iA\_i 求 gcd⁡\gcd,若结果恰好等于 dd,则 dd 是一个可能的最终答案。
    • 时间复杂度:O(na_ilog⁡a_i)O(n \sqrt{a\_i} \log a\_i),因为对每个数分解因数,并在检查时对相关数求一次 gcd⁡\gcd。

    信息

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