CF1818B ndivisible 题解

标签：le frac 题解 奇偶性 CF1818B end 整除 aligned ndivisible

题意简述

• 构造一个长度为 \(n\) 的排列 \(A\)，使得对于任意的 \(l,r\)（ \(1 \le l < r \le n\)）都满足 \(A_l+A_{l+1}+⋯+A_r\) 不可以被 \(r-l+1\) 整除。
• 输出其中一种合法排列即可。

解题思路

构造题。考虑对 \(n\) 进行分类讨论：

• 当 \(n = 1\) 时，由样例即可得合法排列为 \(1\)。
• 当 \(n\) 为大于 \(1\) 的奇数时，因为 \(n-1\) 和 \(n+1\) 必然能被 \(2\) 整除，故不论 \(A\) 如何排列，只需取 \(l=1,r=n\)，必有

\[\begin{aligned} A_l+A_{l+1}+⋯+A_r &= A_1+A_2+⋯+A_n \\ &=\frac{n \times (n+1)}{2} \end{aligned}\]

被 \(r-l+1=n\) 整除。故程序输出 \(-1\)。

• 当 \(n\) 为偶数时，先猜后证。

先猜测构造方案：

首先，取 \(l=i,r=i+1\)（其中 \(1 \le i \le n-1\)），则

\[\begin{aligned} A_l+A_{l+1}+⋯+A_r &= A_i+A_{i+1} \end{aligned}\]

如果 \(A_i,A_i+1\) 同奇偶，则上式为偶数，有可能会被 \(n\) 整除。

所以 \(A_i,A_i+1\) 奇偶性不同（其中 \(1 \le i \le n-1\)）。

其次，取 \(l=i,r=i+2\)（其中 \(1 \le i \le n-2\)），则

\[\begin{aligned} A_l+A_{l+1}+⋯+A_r &= A_i+A_{i+1}+A_{i+2} \end{aligned}\]

同理分析可得排列 \(A\) 不能出现 \(3\) 个连续的数字。

综上所述，一种合法的排列 \(A\) 必须满足以下两点：

1. 相邻的两个数奇偶性不同。
2. 不能出现 \(3\) 个连续的数字。

则猜测答案为形如 \(2,1,4,3,⋯,n,n-1\) 的排列。

再证明其正确性：

考虑分类讨论 \(l,r\) 的奇偶性异同：

1. 当 \(l,r\) 的奇偶性不同时，不妨 \(l\) 为奇数，\(r\) 为偶数，则

\[\begin{aligned} S_{l,r} &= A_l+A_{l+1}+⋯+A_r &= \frac{(l+r) \times (r-l+1)}{2} \end{aligned}\]

因为 \(l+r\) 为奇数，则\(\frac{l+r }{2}\)一定不是整数，那么\(S_{l,r}\)一定不被 \(r-l+1\) 整除。

2. 当 \(l,r\) 的奇偶性相同时，则

\[\begin{aligned} S_{l,r} &= A_l+A_{l+1}+⋯+A_r &= \frac{(l+r) \times (r-l+1)}{2} \pm 1 \end{aligned}\]

与上一种情况相反，因为 \(l+r\) 为偶数，则\(\frac{l+r }{2}\)是整数，那么\((r-l+1)\times (\frac{l+r }{2})\)被 \(r-l+1\) 整除。
则所求 \(S_{l,r}\) 不被 \(r-l+1\) 整除。

证毕！

代码实现

很简单，就不放了

标签：le,frac,题解,奇偶性,CF1818B,end,整除,aligned,ndivisible
From： https://www.cnblogs.com/panxz2009/p/17966122