1 条题解

  • 0
    @ 2026-11-15 21:04:04

    题目分析

    为什么一定有解?

    考虑把所有数全部转移到比如说 a1a_1,最终 a=[K,0,0,…,0]a=[K,0,0,\ldots,0],取 x=Kx=K 即可。

    思路 1

    先分解质因数,xx 的取值只可能是 SS 的质因数。

    然后对每个质因数进行操作,即,使每个数变成 00 或者质因数的 kk 倍。

    先对每堆石头进行处理,处理为该堆石头的数量与它前一个质因数倍数的差值。(当这个数小于质因数,则算它与 00 的差值。)

    比如 [1,2,3,4,5][1,2,3,4,5],S=15S=15,当处理到质因数为 33 的时候,预处理为 [1,2,0,1,2][1,2,0,1,2](这里的 00 意味着已经是质因数的 kk 倍,就可以不存了), 然后贪心一下,对预处理好的数组从大到小排序

    这样我们对预处理好的数组做一下前缀和处理,当某一个时刻,前缀和 = 后缀个数 * 质因数 - 后缀和 的时候,前缀和即为当前答案。

    这里怎么理解呢?其实是:前面的数是用来往外拿,去补后面的数。那么 后缀个数 * 质因数 - 后缀和 也就是把后缀的石堆补到质因数的 (k+1)(k+1) 倍。(之前预处理的是它与质因数 kk 倍的距离)

    思路 2

    记 S=a1+a2+…+anS=a_1+a_2+\ldots+a_n。

    每次操作不改变所有数的总和 SS,仅重新分配数值。因此,最终所有数均为 xx 的倍数时,xx 必须是 SS 的因子(即 x∣Sx \mid S)。

    若 xx 是合数(如 x=4x=4),则其质因子(如 x′=2x'=2)必然也是 SS 的因子。

    将问题转化为 x′x' 的倍数所需的操作次数不会多于 xx 的倍数。因此只需枚举 SS 的所有质因子作为候选 xx 。

    若 SS 本身是质数,则唯一可行的 x=Sx=S。此时最小操作次数为 S−max⁡{ai}S - \max\{a_i\}(将所有数集中到最大值上)。

    对 SS 的每个质因子 xx,计算将所有 aia_i 变为 xx 的倍数的最小操作次数:

    1. 余数处理

      • 计算每项的余数 bi=ai mod xb_i = a_i \bmod x,并保留非零余数(bi=0b_i = 0 无需调整)。
      • 所有非零余数的和 T=∑biT = \sum b_i 必须是 xx 的倍数(否则该 xx 无解)。
    2. 贪心策略:双指针调整余数

      • 排序余数:将非零余数数组 bb 从小到大排序。
      • 双指针调整:
        • 左指针 ll 指向最小余数,右指针 rr 指向最大余数。
        • 每次操作中,从 blb_l 移出 min⁡(bl,x−br)\min(b_l, x - b_r) 到 brb_r:
          • blb_l 减少该值,brb_r 增加该值(若 brb_r 达到 xx 则归零)。
          • 累计操作次数为移出的数值。
        • 更新指针:若 bl=0b_l=0 则 ll 右移;若 br≥xb_r \geq x 则 rr 左移。
      • 正确性:小余数补充大余数至 xx 的倍数,可最小化操作次数 。
    3. 操作次数的计算

      • 最终操作次数为所有移出值的总和,即 cur=∑min⁡(bl,x−br)cur = \sum \min(b_l, x - b_r)。

    复杂度:O(S+knlog⁡n)O(\sqrt{S} + k n \log n)(kk 为质因子数)。

    例如:设 a=[3,5,7]a = [3, 5, 7], S=15S = 15,质因子 x=3x=3 或 55:

    • x=3x=3:余数 b=[0,2,1]b = [0, 2, 1] → 非零余数 [1,2][1, 2]。
      • 排序后 b=[1,2]b = [1, 2],左指针 l=0l=0, 右指针 r=1r=1。
      • 移 min⁡(1,3−2)=1\min(1, 3-2)=1 到 brb_r:bl=0b_l=0, br=3b_r=3(归零)。
      • 操作次数 =1=1。
    • x=5x=5:余数 b=[3,0,2]b = [3, 0, 2] → 非零余数 [2,3][2, 3]。
      • 移 min⁡(2,5−3)=2\min(2, 5-3)=2 到 brb_r:bl=0b_l=0, br=5b_r=5(归零)。
      • 操作次数 =2=2。
    • 最终答案:min⁡(1,2)=1\min(1, 2) = 1。
    • 1

    信息

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