自动搬运

查看原文

来自洛谷，原作者为

	CaptainSlow **

搬运于2025-08-24 21:40:10，当前版本为作者最后更新于2018-09-06 08:17:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

我觉得这题挺好啊...为什么题解都写得这么草率...那就由我来系统地讲解讲解。 （顺带安利一发自己的博客，大家也可以去这里看）

分析

规模较小，直接上可行解DP（有个叫_DYT大佬搞了一波分析证明这个解若存在是小于$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算法。

参考程序

// 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;
}