题解：AT_abc432_c [ABC432C] Candy Tribulation

kuaiCreator · 2025-11-22 15:25:39 · 题解

题目大意

有无限颗糖果一个小糖果重量为 X，一个大糖果重量为 Y。要求给每个小孩都分个大糖果和小糖果使数量之和等于 A_i 且质量之和都相等。

分析

令第 i 个小孩拿到的大糖果数量为 B_i，则小糖果数量为 A_i-B_i，每人拿糖果的质量之和为 W。可得 X\times(A_i-B_i)+Y\times B_i=W。

整理后： B_i=\frac{W-A_i\times X}{Y-X}。

重点：因为每个 B_i 都是整数所以 W \equiv A_i\times X \pmod{Y-X}。

计算 W 的取值范围 \max \limits_{i=1}^n(A_i\times X)\le W\le \min \limits_{i=1}^n(A_i\times Y) 又可通过 A_1 \times X \bmod (Y-X) 计算出余数 r，计算出范围内满足条件的最大的 W 即可，若不存在输出 -1。

获得 W 后可依次计算 \sum\limits _{i=1}^{n}B_i ，注意过程中如果 A[i]\times X \bmod (Y-X) 不为 r 则输出 -1，最后输出 ans 即为答案。