题解：CF1610D Not Quite Lee

· · 题解

前言

这道题给我整崩溃了，没招了，神秘数学题。

题解

考虑好的数列开头是 x，最后面是 x + b_i - 1，则 s_i 是 \frac{b_i \times (2x_i+b_i-1)}{2}。

现在要求 \sum s=0，即 b_i \times (2x_i+b_i-1) = 0，变成 \frac{\sum b_i \times (b_i - 1)}{2} = -\sum b_ix_i。

然后我们通过裴蜀定理知道。

\gcd b_i | \frac{\sum b_i \times (b_i - 1)}{2}

所以。

2 | \frac{\sum b_i \times (b_i - 1)}{\gcd b_i}

我们假设 \gcd b_i = 2^t \times (2k+1)，c_i = \frac{b_i}{2^t}，于是。

2 | \frac{\sum 2^tc_i \times (2^tc_i - 1)}{2^t}

于是

2 | \sum c_i \times (2^tc_i-1)

接着考虑如果 t = 0，那么原式变成 2 | \sum c_i \times (c_i - 1)，等式一定成立，说明含有奇数是随便选的。

如果 t \ge 1，原式变成 2^t \sum c_i^2 - \sum c_i。前面一定是个偶数，而一个数减去另一个数是偶数，说明 \sum c_i 也要是偶数，全选偶数也是合法的。

接着就非常好些了，只要有一个奇数就一定合法，偶数随便选，或者只选偶数。