题解 P2662 【牛场围栏】

· · 个人记录

温馨提示：在博客内观看体验更佳。

学到了一个新的知识点，记录一下。

首先，感谢 @Timsei 对本题的同余类BFS的详细解释。

好吧，事实上这篇博客绝大部分都是搬运过来的。。。

现在，我们来考虑这一题怎么写。

在说这道题目的解法之前，为了叙述方便，我们先给出一些定义：

  1. 剩余系（类）：假设\ m\ 为一个给定的正整数，则我们可以把全体整数分成m个集合：\ K_0,K_1,K_2,...,K_{m-1}\ ,其中对于任意\ r\in \{0,1,2,...,m-1\}\ ，均有\ K_i=\{X\ |\ X\in Z,X\equiv i\ (mod\ m)\}\ ,我们就称\ K_0,K_1,K_2,...,K_{m-1}\ 为模\ m\ 的剩余系（类）。

  2. 完全剩余系：若\ n\ 个数：\ a_1,a_2,a_3,...,a_n\ 种对于任意\ i,j\in \{1,2,3,...,n\}\ 且\ i\ne j\ ，均有\ i\not\equiv j\ (mod\ n)\ （\ i,j\ 不属于模\ n\ 的同一个剩余系），则我们称\ a_1,a_2,a_3,...,a_n\ 为模\ n\ 的完全剩余系，简称完系。

重点现在开始：

这个题目中总共会出现三种情况：

  1. 所有的围栏的长度都可以建造。

  2. 有围栏不能建造，但不存在最大的不能够建造的围栏的长度。

  3. 存在最大的不能够建造的围栏的长度。

我们分别考虑这三种情况：

第一种情况等价于长度为 1 的围栏可以建造，证明如下：

充分性：因为长度为 1 的围栏可以建造，所以对于任意长度 i ，只需要使用 i 个长度为 1 的围栏便可以建造了。

必要性：因为所有的长度的围栏都可以建造，所以长度为 1 的围栏必定可以建造。

对于第二种情况，我们假设我们所有的可以得到的围栏的长度为\ l_1,l_2,l_3,...,ln\ ，则第二种情况等价于\ gcd(l_1,l_2,l_3,...,l_n)>1\ ，证明如下：

充分性：假设\ gcd(l_1,l_2,l_3,...,l_n)=p\ ，则可设对于任意\ r\in \{1,2,3,...,n\}\ ，均有\ l_i=pL_i\ ,则任取这\ n\ 个长度的木棒进行组合，总长\ L=\sum\limits_{i=1}^n{k_il_i}=\sum\limits_{i=1}^n{k_ipL_i}=p\sum\limits_{i=1}^n{k_iL_i}\ ，这意味着\ p\ |\ L\ ，因此对于任意的非\ p \ 倍数的长度，都是不能够建造的。

必要性：若不存在最大值，考虑长度最短的那一根木料，不妨设其长度为\ l\ ，则分别考虑模\ l\ 的每一个剩余类，为了方便表述，我们记\ K_i=\{x\ |\ x\in Z,x\equiv i(mod\ l)\},i\in \{0,1,2,...,l-1\}\ 。

首先，\ K_0\ 中的长度是都可以修建的,要得到\ kr\ 这个长度，只需取\ k\ 根长度为\ l\ 的木料即可。

其次，令\ Q_i\ 为\ K_i\ 中的不能修建的围栏的长度的最大值，\ i\in \{0,1,2,...,l-1\}\ ，则不能修建的围栏的最大长度为\ max\{Q_1,Q_2,Q_3,...,Q_{l-1}\}\ 。

若不存在最大值，则至少有一个剩余类不存在最大值。不妨设\ K_j(j>0,j\in Z)\ 不存在最大值，则可以证明：在\ K_j\ 中的长度都不可能被修建，证明如下：

当\ K_j\ 中存在可以被修建的围栏的长度，取其中最短的长度，不妨设为\ kl+j(k\in Z)\ ，其中\ k\ 必然大于\ 0\ （这一点可以利用\ l\ 的最小性证明），则\ (k-1)l+j\ 为无法修建的围栏长度，且长度为\ (k+u)l+j(u>0,u\in Z)\ 都可以修建，只需要在修建长度为\ kl+j\ 的围栏所用木料的基础上多增加\ u\ 根长度为\ l\ 的木料即可，所以\ K_j\ 中存在最大值，这与我们的假设矛盾。

设模\ l\ 的剩余类中存在最大值的剩余类为\ K_{a_1},K_{a_2},...,K_{a_w}\ ，\ w\ 为存在最大值的剩余类的个数，我们接下来证明\ (a_1,a_2,...,a_w)>1\ 。

先证明一个引理一：若\ (i,j)=1\ ，则取\ 0,i,2i,...,(j-1)i\ ，可以证明这\ j\ 个数模\ j\ 两两不同余，即这\ j\ 个数可以取遍模\ j\ 的完系。证明如下：

若\ pi\ 与\ qi\ 同余，不妨设\ 0\le p<q<j\ ，则\ j\ |\ (qi-pi)\ ，即\ j\ |\ (q-p)i\ ，因为\ (i,j)=1\ ，所以\ j\ |\ (q-p)\ ，而根据我们的假设：\ 0<q-p<j\ ，因而推出了矛盾。因此这\ j\ 个数模\ j\ 两两不同余。

可以推出另一个引理二：若(i，j)=d，i=pd，j=qd，则取0i，1i，…，(q-1)i，可以证明这q个数模q两两不同余，这一点可以直接由上面引理1得到，则这q个数模j分别为0d，1d，…，(q-1)d。

再证一个引理三：i|r，j|r，若(i，j)=1，令S=ai+bj，a,b>=0且a,b∈Z，则S可取遍r的完系。证明如下： 由(p，q)=1，我们可以取i，i2，…，ij这j个数是模j的一个完系，且ij|r，因此S可取遍r的一个完系。

同样我们还可推出一个引理四：i|r，j|r，(i，j)=d，i=pd，j=qd，r=kd，令S=ai+bj，a,b>=0且a,b∈Z，则S可取遍模r分别为0d，1d，…，(k-1)d的剩余类。（由引理3，仿照引理2推得）

依次考虑每一个存在最大值的剩余类Ka1，Ka2，…， Kaw。则对于每一个剩余类Kai，则所有的剩余类Kj都有最大值，其中(r，ai)|j（这一点可由引理2得到），令bi=(r，ai)，则Kbi有最大值。

依次考虑Kb1，K b 2，…， Kbw，令d=(b1，b2，…，bw)，则所有的剩余类Kj都有最大值，其中d|j（这是有引理4得到的）。

因此不存在最大值时，d>1，原先的木料也可以表示为，k*r+bi，因此所有的木料的最大公约数大于1。

所以最大值不存在等价于所有木料长度的最大公约数大于1。

updating