题解：AT_code_festival_final_j 2 Cups

reinforest · 2026-01-27 20:28:52 · 题解

下文中 A=a,B=b,K=k。

显然可以首先令 a 和 b 同时除以 \gcd(a,b)。接下来不妨设 a<b 且 a 和 b 互质。

对于给定的 (a,b)，为了尽量产生新的数字，其有效的操作方式实际上很单一。

例如，令 (a,b)=(3,10)，可能的操作序列有：

可以发现，这相当于在模 b 意义下的运用 2 或者 4 个操作步数让一个数（也就是标蓝的这些数）+a（第一个序列）或者 -a（第二个序列）。

由于 a 和 b 互质，所以当 t \in [0,b-1] \cap \Z 时，ta \bmod b 是两两不同的。考虑设 f(t) 表示现在我们能够在模 b 意义下产生出 a,2a,3a,\cdots,ta 以及 -a,-2a,-3a,\cdots,-ta 的操作步数，那么求出满足 f(t) \leq k 的最大的 t 之后，我们也就能够求出最后的答案。

考虑 f(t) 的求法。可以发现出现“操作步数”为 4 的时候一定出现了“进位”或者“退位”，这些每 \frac{b}{a} 个中括号段就会出现一次，因此对于一个确定的 t 其操作步数就是 2t+\frac{2t}{\frac{b}{a}} 即 2t+2t\frac{a}{b}。

因此 f(t)=2t+2t\frac{a}{b}，具有单调性，可以二分得到 f(t) \leq k 的最大的 t。

确定了这样的 t 之后，能够覆盖的数的总数为 2t+2，因为既可以覆盖正数也可以覆盖“负数”，同时，需要计算 0 与 b 的贡献。

不要忘记之前所说第二种序列的贡献，仅需要判断 f(t)+2 \leq k 即可，即是否能够往后再走 2 步多覆盖一个数。

特判 k=0 以及答案大于 b+1 的情况。