CF1255E2: Send Boxes to Alice (Hard Version)
移动糖果等价于给前缀和加一或减一;枚举总和的质因子 k,把每个前缀和调整到最近的 k 的倍数。来源 Codeforces 1255 E2 · 难度 Codeforces 2100 · 时间 1 s,空间 256 MB · 标签 贪心 / 数学 / 数论 / 前缀和
题目描述
有 个盒子,第 个盒子初始有 颗糖果。一次操作可以把一颗糖果从盒子 移到相邻的盒子 或 。
求最少操作次数,使得存在整数 ,每个盒子中的糖果数都能被 整除;无解输出 。
,,且至少有一个 。
题解
记前缀和
把一颗糖果从盒子 移到 ,只有 减少 ;反向移动则只有 增加 。因此一次操作等价于给某个前缀和加一或减一。
固定 。所有 都能被 整除,当且仅当所有 都能被 整除。于是每个 都要调整到离它最近的 的倍数。记
则调整 的最小代价为
总代价为
由于 单调不减,按同一平局方向取最近的倍数后,调整后的 仍单调不减,所以得到的盒子糖果数非负,方案合法。
总糖果数
必须被 整除。若 ,不存在 ,输出 。
若 是合数,取它的一个质因子 。 的倍数一定是 的倍数,因此对每个 ,到 的倍数的距离不超过到 的倍数的距离,即
所以只需枚举 的不同质因子。对每个质因子 ,按上式在 时间内计算 ,取最小值。
复杂度
分解 为 ;若不同质因子个数为 ,总时间为
空间为 。答案可能超过 位整数范围,需使用 位整数。