题解 P2662 【牛场围栏】
CaptainSlow
2018-09-06 08:17:13
## 前言
我觉得这题挺好啊...为什么题解都写得这么草率...那就由我来系统地讲解讲解。
（顺带安利一发自己的博客，大家也可以去[这里](https://captainslow.cf/2018/09/06/luogup2662-%E7%89%9B%E5%9C%BA%E5%9B%B4%E6%A0%8F/)看）
## 分析
~~规模较小，直接上可行解DP~~（有个叫[_DYT](https://www.luogu.org/space/show?uid=36654)大佬搞了一波分析证明这个解若存在是小于$9 \times 10^6$）
当然我们要考虑更好的解法，如果是初中我也会写可行解DP，当然考场上实在写不出来我还是应该打个暴力骗骗~~满分~~的。
### PART 1 无解？
问题确实可能无解，分两种情况：
> - 存在数字1
> > - 如果有1这个数字，那么所有的数字都可以被表示出来，就不存在不能表示出的数了
> - 所有数的gcd大于1
> > - 设这些数为$A_1, A_2,...,A_n$，设$q=gcd(A_1, A_2,...,A_n)$，则$q|A_1x_1+A_2x_2+...+A_nx_n$($x_1,x_2,...,x_n \in Z$)。这是一个很显然的结论，学习整除的时候是必回讲到的。所以，由于$q > 1$，必然存在不能表示出来的数，即$\forall q \nmid m$，都是不符合条件的数，显然这个$m$是可以到无穷大的。
这两者情况我们可以先特判出来，而剩下的就是$q=1$的情况了，这样的话是肯定存在最大的不能表示出来的数的。
这个很显然。
### PART 2 寻找
我们如何去寻找这个最大的不能被表示出来的数呢？
我们考虑所有可以被表示出来的数构成的数集$S$，由最小数原理可知，$S$中一定存在最小的$s_0$。考虑模$s_0$的每一个剩余系，记为$K_i=\lbrace x|x \equiv i\pmod{s_0}\rbrace,i=0,1,2,...,s_0-1$。
显然$s_0=min(A_i)$。对$\forall K_i$，由最小数原理，存在最小的能被表示出来的$t_i$，$t_i=s_0*p+i$，显然$p>0$，否则与$s_0$的最小性矛盾。那么对每一个$K_i$，最大不能被表示出来的数就是$s_0*(p-1)+i$。这样，问题就转化为了求每一个这样的$t_i$，这时候，我们就引入这个被称为剩余系最短路的算法了。我们可以把每个剩余系$K_i$抽象为图中的点，那么连接它们的边就是$A_i$中的那些数。然后就用普通的最短路更新方式就可以了。我选择了用Dijkstra算法。
## 参考程序
```cpp
// Luogu P2262
#include <cstdio>
#include <cstring>
#include <algorithm>
const int ARSIZE = 4005;
const int INF = 0x7f7f7f7f;
int N, M, L[ARSIZE], tot_l = 0, Q[ARSIZE];
bool exist[ARSIZE] = {0}, used[ARSIZE] = {0};
inline int gcd(int a, int b) {
for (a < b ? std::swap(a, b) : (void)0; b; std::swap(a, b)) a %= b;
return a;
}
int dijkstra();
int main() {
scanf("%d%d", &N, &M);
int j, li, gd = 0;
for (int i = 0; i < N; i++) {
scanf("%d", &li);
gd = gcd(gd, li);
for (j = 0; j <= M && j < li; j++) exist[li - j] = true, gd = gcd(li - j, gd); // 很多人WA，半天查不出错，很可能就是只算了所有L[i]的gcd
}
if (exist[1] || gd > 1) puts("-1");
else printf("%d\n", dijkstra());
return 0;
}
int dijkstra() {
memset(Q, 0x7f, sizeof(Q));
int i, v, k;
for (Q[0] = 0, i = 2; i <= 3000; i++) // 初始化
if (exist[i]) L[tot_l++] = i;
int MOD = L[0];
while (true) {
for (i = 0, k = -1; i < MOD; i++)
if (!used[i] && (k == -1 || Q[i] < Q[k])) k = i;
if (k == -1) break;
used[k] = true;
for (i = 1; i < tot_l; i++)
if (!used[v = (k + L[i]) % MOD]) Q[v] = std::min(Q[v], Q[k] + L[i]); // 更新其他剩余系
}
int res = -1;
for (i = 1; i < MOD; i++) res = std::max(res, Q[i] - MOD);
return res;
}
```