一、引言：问题的起源

在算法竞赛的数学部分中，同余理论是一个重要部分。它以一种优雅的方式将无限的整数世界映射到有限的剩余类中，为我们处理与整除、余数、周期性相关的问题提供了独特的视角。而当我们将同余理论与图论中的最短路算法相结合时，一个精巧的算法模型——同余最短路——便应运而生。

这个模型专门解决一类特定形式的问题：给定个正整数，问它们通过非负整数系数的线性组合 () 能够表示出哪些数？或者，不能表示出的最大数是多少？或者，在某个区间内能表示出多少个数？

这类问题最经典的形式或许是“购物凑单”或“邮票面值”问题，更学术化的名称是**弗罗贝尼乌斯硬币问题 (Frobenius Coin Problem)**。

弗罗贝尼乌斯硬币问题:
给定一组互质的正整数，求不能由这组数的非负整数线性组合构成的最大整数。这个最大数被称为弗罗贝尼乌斯数，记作。

当时，问题有著名的结论：。但当时，不存在简单的封闭解公式。

如果我们尝试用动态规划来解决，可能会定义表示数值是否可以被凑出。状态转移方程为。这个方法直观，但当我们需要求解的目标数值范围非常大时（例如），的复杂度显然无法接受。数组根本开不下。

这正是同余最短路大显身手的舞台。其核心思想在于，我们不需要关心每一个具体的数值，而是关心这些数值在模某个数意义下的“性质”。通过将无限的数值集合根据余数进行分组，我们将一个看似无限的问题转化为了一个在有限顶点图上的最短路问题。

二、核心思想：构建同余图

同余最短路的威力源于其巧妙的建模过程。我们将一步步拆解这个过程，揭示其背后的数学原理。

1. 选取模数

我们的目标是利用同余的性质来压缩状态。第一步，也是最关键的一步，是选取一个模数。理论上，任何大于1的整数都可以作为模数，但为了让模型更有效，我们通常选择给定的个整数中的一个，一般是最小的那个，我们不妨设为。

为什么选择？

状态压缩：我们即将把所有整数按模的余数分为个类。选择最小的作为模数，意味着我们将要构建的图的顶点数最少，从而降低了算法的时空复杂度。
结构简化：将作为模数后，它在模型中的角色会变得特殊而简单，我们只需要关注其他个数的影响。

2. 定义图的顶点

选定模数后，我们将所有非负整数按模的余数分成了个剩余类。这个剩余类就是我们图中的顶点。

**顶点集合 **：。
顶点的含义：顶点代表所有形如 () 的整数集合。例如，如果，顶点就代表这个集合。

3. 定义图的边与权值

我们的目标是找到能被凑出的数。考虑一个已经被凑出的数。如果我们再选择一个数 (其中 ) 加上去，就得到了一个新的、可以被凑出的数。

这个加法操作在我们的同余图上如何体现呢？

设。
那么。

这意味着，从一个属于剩余类的数，通过加上，我们可以“跳”到一个属于剩余类的数。这个“跳跃”的过程，就是图中的一条有向边。

**边的集合 **：对于图中的任意一个顶点，以及给定的任意一个整数 ()，我们都构建一条有向边。
**边的权值 **：这个跳跃的“代价”是多少呢？我们为了实现这个状态转移，付出的代价是加上了数值。所以，这条边的权值就是。

至此，一个带权有向图已经构建完成。这个图有个顶点，最多有条边。

4. 最短路的含义

图建好了，但最短路是什么？它和我们最初的问题有什么关系？

让我们重新定义一下我们要求解的目标。对于每一个剩余类，我们想知道，能被凑出的、且模余的那个最小的数是多少？

我们将这个最小数记为。

如果存在，那么任何其他模余的数 (其中 )，是否也能被凑出呢？答案是肯定的。因为是的倍数，而本身就是可用的“硬币”。所以我们可以通过在的基础上加若干个来得到。
因此，成为了一个分界点。对于所有模余的数，小于的都凑不出来，大于等于的都能凑出来。

现在，我们把和图论中的最短路联系起来。

**源点 (Source)**：我们从哪里开始凑数？自然是从开始，不选任何数时的总和是。数字模余。所以，我们可以不费任何代价地“得到”一个在剩余类中的数，这个数就是本身。因此，我们将图的源点设为顶点，并且它的初始“距离”为。
的图论解释：正是从源点出发，到达顶点的最短路径长度。

为什么？
考虑一条从源点到顶点的路径：。
这条路径对应的操作是：从初始值开始，依次加上一系列的。例如，路径。
路径的总长度（所有边权之和）就是。
这条路径的终点是，意味着路径长度。
最短路算法（如Dijkstra）正是为我们寻找一个总和最小的边权序列，使得从源点出发能到达顶点。这个最小的边权和，恰好就是我们定义的“能被凑出的、且模余的最小的数”。

5. 算法流程总结

现在，我们可以将整个算法流程串联起来：

预处理：在给定的个数中，找到最小的数，记为。不妨假设。
建图：
- 创建一个包含个顶点的图，编号为。
- 对于每个顶点和每个 ()，添加一条从到的有向边，边权为。
初始化：
- 创建一个距离数组，大小为。
- 。
- 对于所有。
求解：
- 以顶点为源点，在该图上运行一次单源最短路算法。
- 由于所有边权都是正数，使用 Dijkstra 算法是最高效的选择。
解释结果：
- 算法结束后，的值就是能被凑出的、模余的最小非负整数。
- 如果某个仍然是，说明任何模余的数都无法被凑出。这种情况仅在时才可能发生。若，则所有能凑出的数都必须是的倍数，因此那些模余数不是的倍数的顶点将不可达。

这个模型的时间复杂度主要由 Dijkstra 算法决定。使用优先队列优化的 Dijkstra，时间复杂度为。在我们的图中，, 。所以总时间复杂度为。空间复杂度为，用于存储图和距离数组。

三、经典模型与代码实现

我们通过一个具体问题来实践同余最短路的核心思想。这个问题完美地诠释了如何将一个看似与图论无关的数论问题，转化为高效的最短路求解。

问题：跳楼机 (洛谷 P3403)

题意概括:
你在一座层高的大楼的第1层。有三种移动方式：向上移动层、向上移动层、向上移动层。问你总共能到达多少个不同的楼层（包括第1层）。

解题思路

这个问题可以被转化为：求形如的数值，在不超过的前提下，有多少种不同的取值。其中为非负整数。

这等价于求解：非负整数线性组合在满足的条件下，有多少个不同的取值。这就是一个典型的、可以用同余最短路解决的区间计数问题。

选取模数: 我们从中选择最小的一个作为模数。为了方便，我们先将这三个数排序，令为另外两个数。我们选择。
构建模型:
- 顶点: 我们的图有个顶点，编号为。顶点代表所有可以通过组合出的、模余的数值集合。
- 最短路含义: 我们定义为，能凑出的、模余的最小数值。
- 边: 我们从数值开始构造。如果当前已经能凑出数值，再向上走层，就得到。这个操作在图上体现为一条边。对于任意顶点，我们连接两条边：
  - 一条从指向，边权为。
  - 一条从指向，边权为。
    为什么不考虑？因为是模数，它的作用是填充。一旦我们得到了模余的最小数，所有其他模余的可达数都可以通过在的基础上加若干个得到。这个填充步骤在最后统计答案时处理。
运行Dijkstra:
- 以顶点为源点，因为不进行任何移动时，我们能达到的数值是 (对应楼层是1)，它模余。所以。
- 其他所有初始化为无穷大。
- 运行一次Dijkstra算法，计算出从源点到所有其他顶点的最短路径长度，即的值。
计算最终答案:
- 算法结束后，就是能凑出的、模余的最小偏移量。对应的楼层是。
- 对于每个余数，所有可达的、模余的偏移量为。
- 我们要统计这些偏移量中有多少个小于等于。
- 如果，那么这个余数对应的所有楼层都无法到达，贡献为。
- 如果，那么满足条件的偏移量为。解得。
- 由于是非负整数，它可以取。总共有个值。
- 将所有余数的贡献累加起来，即为总共可以到达的楼层数。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005; // 模数的最大值
const ll INF = 4e18;  // h可能很大, 无穷大也要足够大

ll h;
ll a[3];
ll d[N];
bool v[N];

void dijk() {
    for (int i = 1; i < a[0]; ++i) d[i] = INF; // 初始化距离
    d[0] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0}); // {距离, 顶点}

    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int u = p.second;

        if (v[u]) continue; // 若已访问则跳过
        v[u] = true;

        // 尝试用另外两个数进行扩展
        for (int i = 1; i < 3; ++i) {
            int nxt = (u + a[i]) % a[0];
            ll w = a[i];
            if (d[nxt] > d[u] + w) {
                d[nxt] = d[u] + w;
                pq.push({d[nxt], nxt});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> h;
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3); // 排序, 使 a[0] 为最小值

    dijk();

    ll ans = 0;
    for (int i = 0; i < a[0]; ++i) {
        if (h > d[i]) { // 对应的楼层是 1+d[i], 要求 1+d[i] <= h
            ans += (h - 1 - d[i]) / a[0] + 1;
        }
    }
    cout << ans << endl;

    return 0;
}

代码解释
- a 数组存储，排序后 a[0] 作为模数。
- d[i] 存储凑出模 a[0] 余 i 的最小数值和。
- dijk 函数实现了Dijkstra算法，用 a[1] 和 a[2] 作为图的边权进行松弛操作。
- 最终答案的计算中，h > d[i] 判断了最小可达楼层 1+d[i] 是否在范围内。h-1 是偏移量的上限。
- (h - 1 - d[i]) / a[0] + 1 计算了在余数 i 这一类中，有多少个可达的楼层。
复杂度分析
- 时间复杂度: 。其中是中的最小值。图的顶点数是，边数是。Dijkstra算法的复杂度为。
- 空间复杂度: 。主要由距离数组 d、访问数组 v 和优先队列 pq 决定。

问题：墨墨的等式 (国家集训队)

题意概括:
给定个非负整数和一个区间。求有多少个整数，使得关于的方程存在非负整数解。

解题思路

这个问题等价于，求由集合中元素的非负整数线性组合所能表示出的数，在区间内有多少个。这与“跳楼机”问题本质相同，是一个标准的同余最短路区间计数应用。

预处理与模数选择:
- 方程中的项对能表示出的数值集合没有贡献（除了0本身，但本题区间从1开始），可以忽略。
- 我们从所有正的中，选取最小的那个作为模数。将这个最小数记为 a[0]。
构建模型与求解:
- 与前例完全一致，我们构建一个以为顶点的图。
- 表示能凑出的、模余的最小值。
- 以为源点，用其他 () 作为边权，运行Dijkstra算法，求出所有的。
区间统计:
- 我们的目标是计算区间内的可达数。直接计算区间较为繁琐，我们可以利用前缀和思想，将问题转化为 count(r) - count(l-1)，其中 count(T) 函数计算在闭区间内有多少个可达数。
- count(T) 的计算方法如下：
  - 遍历所有余数。
  - 对于每个，最小可达数是。
  - 如果，那么在内，这个剩余类贡献的可达数有只要它们。
  - 数量为。
  - 将所有余数的贡献累加即可。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 500005; // 模数最大值
const ll INF = 1e18;   // 距离无穷大

int n;
ll l, r;
ll a[15];
ll d[N];
bool v[N];

void dijk() {
    for (int i = 1; i < a[0]; ++i) d[i] = INF;
    d[0] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int u = p.second;

        if (v[u]) continue;
        v[u] = true;

        for (int i = 1; i < n; ++i) {
            int nxt = (u + a[i]) % a[0];
            ll w = a[i];
            if (d[nxt] > d[u] + w) {
                d[nxt] = d[u] + w;
                pq.push({d[nxt], nxt});
            }
        }
    }
}

// 计算[0, T]区间内可凑出的数的数量
ll cnt(ll T) {
    if (T < 0) return 0;
    ll res = 0;
    for (int i = 0; i < a[0]; ++i) {
        if (d[i] <= T) {
            res += (T - d[i]) / a[0] + 1;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int nn; // 临时存储原始n
    cin >> nn >> l >> r;
    for (int i = 0; i < nn; ++i) {
        ll x;
        cin >> x;
        if (x > 0) a[n++] = x; // 过滤掉0
    }

    if (n == 0) { // 如果没有正的a_i
        cout << 0 << endl;
        return 0;
    }
    
    sort(a, a + n);
    n = unique(a, a + n) - a; // 去重

    dijk();

    cout << cnt(r) - cnt(l - 1) << endl;

    return 0;
}

代码解释
- 程序首先读入数据，并过滤掉所有为0的，因为它们对构造正整数没有帮助。
- 接着对有效的排序并去重，a[0] 自然成为最小的非零系数，被用作模数。
- dijk 函数的逻辑与前例相同，构建并求解同余最短路模型。
- cnt(T) 函数实现了计算区间内可达数数量的逻辑。
- 最终答案通过 cnt(r) - cnt(l - 1) 计算得出，体现了前缀和思想。
复杂度分析
- 时间复杂度: 。其中是所有正中的最小值。Dijkstra算法是主要耗时部分。
- 空间复杂度: 。用于存储图相关的数组。

四、模型变种与拓展

掌握了基本模型后，我们来看一些常见的变种。同余最短路的强大之处在于其模型的灵活性，通过微调图的定义或最终答案的计算方式，可以解决一系列相关问题。

变种一：区间内可表示数的数量

题意概括:
给定个正整数和一个上限。问在闭区间内，有多少个整数可以被这个数通过非负整数线性组合表示出来？

解题思路

这个问题的前半部分与之前完全相同。我们依然需要求解出每个剩余类能被凑出的最小值。

运行同余最短路: 照常选取最小的数作为模数，运行Dijkstra算法，得到所有。
分剩余类统计: 对于每个剩余类：
- 我们知道，这个类中能被表示的数是。
- 我们需要统计这些数中有多少个是小于等于的。
- 首先，如果，那么这个剩余类中所有能被表示的数都大于，对答案的贡献是。
- 如果，那么能被表示的数是。
- 解不等式，得到。
- 由于是非负整数，所以可以取。
- 总共有个可行的值。
- 因此，对于这个剩余类，在区间内（如果，它本身不在[1,T]内，但我们通常求的是总价值，如果题目严格要求在[1,T]内，计算时需注意）能表示的数的数量就是。
汇总答案: 将所有剩余类的贡献加起来，就是最终答案。

如果题目要求的是，而我们算出的了，那么总数需要减1（如果）。不过一般这类问题求的是能凑出的价值种类数，0是否计入看题意。我们这里的代码将计算所有小于等于T的非负整数。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
const ll INF = 4e18; // T可能很大，INF也要相应增大

int n;
ll t;
ll a[55];
ll d[N];
bool v[N];

void dijkstra() {
    for (int i = 1; i < a[0]; ++i) d[i] = INF;
    d[0] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int u = p.second;

        if (v[u]) continue;
        v[u] = true;

        for (int i = 1; i < n; ++i) {
            int nxt = (u + a[i]) % a[0];
            ll w = a[i];
            if (d[nxt] > d[u] + w) {
                d[nxt] = d[u] + w;
                pq.push({d[nxt], nxt});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    // 过滤掉重复和大于最小值的数没有意义，但为了普适性这里保留
    sort(a, a + n);
    // 可选：去重，如果a数组有重复元素
    n = unique(a, a + n) - a;


    dijkstra();

    ll ans = 0;
    for (int i = 0; i < a[0]; ++i) {
        if (t >= d[i]) {
            ans += (t - d[i]) / a[0] + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

代码注释与解释
- 前半部分的Dijkstra与前一示例完全一致。
- 核心区别在于 main 函数的后半部分。
- 我们遍历所有剩余类。
- 对于每个，检查 d[i] (即 ) 是否超过了上限 t。
- 如果 t >= d[i]，则计算这个类对答案的贡献 (t - d[i]) / a[0] + 1，并累加到 ans。
- unique 函数在这里是可选的，但如果输入数据可能包含重复的数值，这是一个好习惯。它将重复的元素移动到数组末尾并返回一个指向不重复范围末尾的迭代器。
复杂度分析
- 时间复杂度: 。瓶颈依然是Dijkstra算法。
- 空间复杂度: 。

变种二：带限制的组合 (初步探讨)

一个更复杂也更常见的拓展是，当某些或所有物品的数量是有限的时候，问题就从“无限背包”过渡到了“多重背包”。如果物品的种类、数量、以及背包容量都很大，经典的多重背包DP（无论是二进制拆分还单调队列优化）都会失效。

同余最短路可以与背包DP结合，形成一种强大的“混合”解法。

问题雏形:
假设有种物品，其中种物品（价值为）可以无限使用，但第1种物品（价值为）只有个。问能凑出的总价值有多少种？

这是一个简化的混合背包问题。直接使用同余最短路模型会遇到困难，因为我们不能再无限制地使用来填充剩余类内部的空隙了。

思路转换：
既然的使用受限，那我们就不应该选它作为模数。模数的选择应该是那些可以被无限次使用的物品之一。我们选择 (假设它是无限物品中价值最小的) 作为模数。

第一步: 暂时忽略受限物品。对所有无限物品运行同余最短路。
- 模数。
- 图的顶点是。
- 边是基于构建的。
- 运行Dijkstra后，得到，表示仅使用无限物品时，凑出模余的数的最小代价。
第二步: 引入受限物品的影响。
- 现在我们有个可以使用。这个可以看作是一个独立的多重背包问题。
- 我们可以定义一个新的DP状态，例如表示使用了个后，凑出的数模余的最小代价。但这似乎又回到了二维DP的复杂境地。

一个更巧妙的视角是，把对的使用看作是在同余图上的“二次更新”。

初始时，我们有数组。
现在考虑增加一个。对于图上任意一个顶点，如果我们当前能凑出的最小代价是，那么加上一个后，我们就到达了这个状态，代价是。
这不就是又一次松弛操作吗？
我们可以把个的使用过程，看成轮更新。但这样做效率不高。

正确的处理方式通常是分层图或者直接在DP状态上想办法。让我们考虑一个更直接的DP。
令表示凑出模余的总价值的最小值，这次**允许使用 **。
显然，初始时 (完全不使用 )。
然后我们用来更新这个数组。这是一个典型的“用物品更新DP数组”的背包过程。
我们可以把个进行二进制拆分，变成个物品，然后对每个拆分出的物品，做一次全图的松弛：
for (int i = 0; i < m; ++i) f[(i + k*a1)%m] = min(f[(i + k*a1)%m], f[i] + k*a1);
但这需要保证更新顺序，以防一个物品被重复使用。正确的背包式更新应该是 for (int i = m-1; i>=0; --i) 的倒序循环（01背包思想）。

更高效的做法是利用单调队列。对于这个物品的更新，我们可以按模的余数对所有顶点分组。在每个组内，更新就成了一个滑动窗口最小值问题，可以用单调队列在时间内完成。

五、同余最短路与背包问题的深度融合

之前我们探讨了所有物品数量都无限的理想情况。然而，在更具挑战性的问题中，往往会出现部分物品数量有限，部分物品数量无限的混合背包模式。当数据规模使得传统动态规划方法（如二进制拆分、单调队列优化多重背包）因状态空间过大而失效时，同余最短路便成为了破局的关键。

其核心思路是：利用同余最短路处理无限物品，再将有限物品视作对结果的“扰动”或“更新”。

题意概括:
给定种物品，其中种物品（价值为，数量为）是有限的，另外种物品（价值为）是无限的。求能凑出的最大不可达价值，或是在某个范围内能凑出多少种价值。

为了简化模型，我们通常选择一个无限物品的价值作为模数，假设是（无限物品中价值最小的那个）。

基础框架: 首先，完全不考虑有限物品，只用无限物品跑一次同余最短路。得到数组，表示仅用无限物品凑出模余的最小代价。这是我们的初始状态。
引入有限物品: 现在，我们要把有限物品的效果加进来。假设有一个有限物品，价值为，数量为。我们可以用它来更新当前的数组。一个朴素的想法是，对于每个，做次更新，每次更新都像01背包一样遍历所有状态。这等价于对每个物品做次01背包。

更进一步，我们可以用二进制拆分把数量为的物品拆成个独立的01背包物品。对于每个拆分出的价值为的物品，我们对整个数组做一次更新：

为了避免一个拆分出的物品在一个更新轮次中被多次使用，这个更新需要倒序遍历。这个方法可行，但当有限物品种类较多时，复杂度依然可能很高。

最高效的方法是利用单调队列。

单调队列优化更新

当我们引入一个价值为、数量为的有限物品时，对数组的更新过程可以被形式化。对于任意一个余数，新的可以由哪些状态转移而来？
它可以由原来的，或者，或者，…，最多到转移而来。
即：

这个式子具有明显的滑动窗口最小值的特征，是单调队列优化的绝佳场景。

具体操作如下：
我们将所有顶点按照模的余数分组。令。我们把顶点分到第组。
为什么这么分组？因为在一个组内，例如所有模余的顶点，它们通过不断加上或减去（模意义下），形成的转移路径是封闭的。从出发，加变成，再加变成，… 这个序列中的所有顶点模都余。

因此，对价值为的物品的更新，只会在这些组内部独立进行。

对于每个组 :

构造一个序列，包含该组的所有顶点：。
对于这个序列上的每一个点，我们要求。
这是一个标准的滑动窗口问题。窗口大小为。我们需要求窗口内 d[v] - k*b 的最小值，其中 v 是窗口内的点，k 是从窗口起点开始的偏移量。
使用单调队列，对每个组的更新可以在线性时间内完成。

总的更新复杂度：对于一个价值为的物品，分组后用单调队列优化，总复杂度为。如果有个种有限物品，总复杂度就是。

示例：[Codeforces 510D] Fox And Jumping

题意概括:
有张卡片，每张卡片有一个数字。还有一个代价。你可以选择一个卡片子集。所选子集的必须为 1。求满足条件的子集的最小总代价。

这个问题看起来和同余最短路关系不大，但我们可以转换视角。
题目要求。我们可以枚举最终的值。但这是不行的。
换个思路，我们要求。这等价于，对于所有素数，都存在一个选中的使得。这个条件太复杂了。

让我们回到问题的核心：我们选择了一些卡片，它们的。这其实是一个状态压缩DP的经典模型。令表示所选卡片数字的包含 mask 所代表的素因子时的最小代价。这个 mask 太大了。

正确的打开方式是发现很小（例如）。我们可以选择一张卡片作为“基准”，然后尝试用其他卡片去“凑”出。
假设我们选择了第张卡片，其数字为，代价为。现在我们已经付出了的代价，手里拥有的数字的是。我们的目标是再加入一些卡片，使得最终的变成。
这等价于，我们需要用其他卡片凑出一个数，使得。
这个问题可以转化为：我们有一堆物品，价值是，代价是。我们想凑出一个总价值，使得，并且总代价最小。

这依然很复杂。但同余最短路提供了一个全新的视角。
我们将问题看作一个最短路问题。

顶点: 的所有可能值。由于，因子可能很多。不行。

让我们换个角度。如果我们将一张卡片的代价看作是边权，那么我们是在一张图上找一条路径。

状态/顶点: 当前已选卡片集合的。
初始状态: 可以选择任意一张卡片作为起点，当前状态为，代价为。
状态转移: 如果当前状态为（即），再选一张卡片，新状态为，总代价增加。
目标: 找到一条从某个初始状态到状态的最短路。

这正是一个最短路问题！图的顶点是所有可能出现的值。我们可以用 Dijkstra 算法求解。

图的顶点: 所有的因子。
距离数组: d[g] 表示使得当前为的最小代价。
Dijkstra流程:
1. 初始化 d[g] = infinity for all g, d[0] = 0 (或者一个虚拟源点)。
2. 将所有卡片作为初始路径：对于每张卡片，d[l_i] = min(d[l_i], c_i)，并将 (c_i, l_i) 压入优先队列。
3. 跑 Dijkstra。每次取出 (cost, g)，遍历所有卡片，用 d[g] + c_j 更新 d[gcd(g, l_j)]。

这个做法的顶点数是所有的因子数，太多了。但是，我们发现一个重要的性质：每次转移 g -> gcd(g, l_j)，g 只会变小或不变。这提示我们也许不需要完整的 Dijkstra。
我们可以将所有卡片按代价从小到大排序。
但最直接的同余最短路模型是：
选择一个数作为模数。顶点是。表示凑出的数模余的最小代价。
这个题中，每个物品的代价不同，不能直接作为边权。
应该表示凑出模余的数所需要的最小代价和。

模数: 选谁？选？
边: 对于每个顶点，以及每张卡片，连边，边权为。
源点: 。。
跑 Dijkstra，得到。现在我们有了一系列（余数，最小代价）对。
对于每个，我们知道凑出模余的数至少需要的代价。我们凑出的实际数值是。我们不知道具体是多少，只知道且是通过价值总和为的卡片凑成的。
这似乎无法处理条件。

这道题的正确解法是状态为的最短路，而非典型的同余最短路。但其思想有相通之处：将一个组合优化问题映射到图上求最短路。

让我们回到一个更标准的混合背包问题。

题意概括:
有种物品。一种价值为的大物品，无限量。种价值为，数量为的小物品。给定背包容量，问不超过的容量，最多能装多大价值的物品？

无限物品处理: 大物品是无限的，选它作模数。
有限物品处理: 小物品是有限的。我们定义为只用小物品，凑出价值模余时，所需的最小实际价值。初始时。
多重背包DP: 对于每一种小物品，我们用它来更新数组。这是一个多重背包问题，可以用单调队列优化。
- for 每一个小物品
- for from to
- 用单调队列更新组内的值。
最终统计: 经过所有小物品的更新后，存储了只用小物品凑出模余的最小总价值。
现在考虑大物品。对于每个余数，我们已经用价值的小物品凑出了模余。如果，那么我们可以用大物品来填充剩余的容量。
我们可以填充个大物品。总价值是。
这个值等于。
最终答案就是。

C++ 代码实现 (混合背包)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005; // 模数 W 的最大值
const ll INF = 1e18;

ll d[N];
int n, m; // n-1种小物品, 模数m
ll V;

// 单调队列 q 存储下标，维护 d[j] - j/w * w 的最小值
int q[N]; 
ll val[N];

void solve(int w, int c) {
    int g = __gcd(w, m);
    for (int r = 0; r < g; ++r) {
        int head = 0, tail = 0;
        int sz = (m - 1 - r) / g + 1;
        for (int i = 0; i < sz; ++i) {
            int u = r + i * g; // 当前顶点
            // val是我们要比较的值
            val[u] = d[u] - (ll)i * w;
            
            // 维护单调队列
            while (head < tail && val[q[tail-1]] >= val[u]) {
                tail--;
            }
            q[tail++] = u;
            
            // 移除过期队首
            if ((u - q[head]) / g > c) {
                head++;
            }
            
            // 用队首更新当前d[u]
            if (head < tail) {
                d[u] = min(d[u], val[q[head]] + (ll)i * w);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> V >> m;
    for (int i = 1; i < m; ++i) d[i] = INF;
    d[0] = 0;

    for (int i = 0; i < n; ++i) {
        int w, c;
        cin >> w >> c;
        solve(w, c);
    }
    
    ll ans = 0;
    for (int i = 0; i < m; ++i) {
        if (d[i] <= V) {
            ans = max(ans, V - (V - d[i]) % m);
        }
    }
    cout << ans << endl;

    return 0;
}

代码解释:
- m 是无限物品的价值，作为模数。V 是背包总容量。
- d[i] 含义如上所述。
- solve(w, c) 函数用一个数量为 c 价值为 w 的物品来更新 d 数组。
- 内部按 __gcd(w, m) 分组。
- 对每个组，我们遍历其中的点 u。u 可以看作是链上的第 i 个点。我们要找的是 d[u-j*g] 的某个最优值。通过变换 d[u] = min(d[u_k] + (i-k)*w)，转化为求 min(d[u_k] - k*w) + i*w。所以单调队列维护 d[u_k] - k*w 的最小值。
- val[u] = d[u] - (ll)i * w 就是这个要维护的值。
- 最终的答案统计逻辑如理论推导。
复杂度分析:
- 时间复杂度: 每个有限物品的更新是。若有个有限物品，则为。
- 空间复杂度: 。

六、另一视角：分层图与状态扩展

同余最短路本质上是一种状态压缩，将无穷多的整数值压缩到个剩余类中。当问题包含额外的约束维度时，我们可以通过分层图来扩展状态。

分层图最短路是一种建模技巧，当图中边的使用会消耗某种资源，或者通过边时会改变某种状态时，可以把这个资源/状态维度加入到图的顶点表示中。

问题雏形:
给定个整数和一个特殊操作。普通操作是加上任意一个，代价为。特殊操作可以执行最多次，例如，将当前值翻倍，代价为。求凑出某个目标值的最小代价，或能凑出的值的某些性质。

这里，除了当前值的余数外，我们还需要记录特殊操作的使用次数。

状态: ，表示当前凑出的值模余，且已经使用了次特殊操作。
图的顶点: 顶点集合是。图的大小是。
图的边:
1. 普通边: 对于每个状态，以及每个，连接一条边到，边权为。这代表不使用特殊操作，只在第层内部转移。
2. 特殊边/层间边: 对于每个状态，如果，可以执行一次特殊操作。假设操作是将值变成，代价为。那么我们连接一条从到的边，边权为。
  - 这里的是个麻烦点。如果的值依赖于本身而不仅仅是，比如，那么新状态的余数是。但我们只知道，不知道的确切值。
  - 。所以新余数是。这是一个从一个状态连接到另一个状态的边。
  - 这种边的终点依赖于当前的最短路长度，这意味着图的结构是动态变化的。这使得标准的 Dijkstra 算法失效。

但是，如果特殊操作对余数的影响是固定的，问题就简化了。
例如，特殊操作是“加上一个特殊的数值 ”，代价为。

层间边: 从到，边权为。

示例: 小明的游戏 (洛谷 P4554)

题意概括:
在一个的棋盘上，分布着两种类型的格子。从一个起点移动到终点，规则如下：移动到相邻的同类型格子，花费为0；移动到相邻的不同类型格子，花费为1。求从起点到终点的最小总花费。

此问题虽然不涉及数论，但它完美地展示了另一个与最短路算法紧密相关的重要思想：根据图的特性选择最高效的算法。同余最短路的核心引擎是Dijkstra算法，但当图的边权结构非常特殊时（例如本题中只有0和1），我们可以采用更为高效的专门算法，如0-1广度优先搜索。

解题思路

这是一个典型的边权仅为0或1的最短路问题。对于这类问题，使用双端队列（deque）实现的0-1广度优先搜索（BFS）是最佳选择。它比标准的Dijkstra算法（使用优先队列）效率更高。

状态与距离: 状态就是棋盘上的坐标 (x, y)。我们用数组 d[x][y] 记录从起点到 (x, y) 的最小花费。
0-1 BFS 核心:
1. 创建一个双端队列 q。
2. 将起点入队，其距离 d[sx][sy] 初始化为0。
3. 从队列头部取出一个状态 (x, y) 进行扩展。
4. 遍历其所有相邻格子 (nx, ny)：
  - 计算移动的费用 w (如果格子类型不同则 w=1，相同则 w=0)。
  - 如果发现一条更短的路径 (即 d[nx][ny] > d[x][y] + w)，则更新 d[nx][ny]。
  - 关键：如果 w=0，将 (nx, ny) 插入到队头；如果 w=1，则插入到队尾。
原理: 将0花费的移动插入队头，保证了队列中的节点始终按距离大致有序。任何时候，队头元素的花费总是最小的（或与之后元素相等），这使得我们可以像普通BFS一样处理节点，而不需要优先队列的对数时间开销。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 505;
const int INF = 1e9;

int n, m;
char g[N][N];
int d[N][N];

void bfs(int x1, int y1, int x2, int y2) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            d[i][j] = INF;
        }
    }

    deque<pair<int, int>> q;

    d[x1][y1] = 0;
    q.push_front({x1, y1});

    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop_front();

        if (x == x2 && y == y2) return; // 已到达终点

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            int w = (g[x][y] != g[nx][ny]); // 计算移动花费
            
            if (d[nx][ny] > d[x][y] + w) {
                d[nx][ny] = d[x][y] + w;
                if (w == 0) {
                    q.push_front({nx, ny}); // 0花费, 插入队头
                } else {
                    q.push_back({nx, ny});  // 1花费, 插入队尾
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    while (cin >> n >> m && (n || m)) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> g[i][j];
            }
        }
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        bfs(x1, y1, x2, y2);
        cout << d[x2][y2] << endl;
    }
    return 0;
}

代码解释
- 主函数处理多组测试数据，循环直到输入 n=0, m=0。
- bfs 函数实现了0-1广度优先搜索。
- 使用 deque 作为核心数据结构。
- d[x][y] 存储到达 (x, y) 的最小花费。
- 松弛操作后，根据花费 w 的值决定新节点是从队头还是队尾入队。
复杂度分析
- 时间复杂度: 。每个格子最多入队出队一次，每次扩展是常数时间。
- 空间复杂度: 。主要由距离数组 d 和双端队列 q 占用。

七、实践中的考量与陷阱

理论是完美的，但实践中总会遇到各种细节问题。

1. 模数的选择

常规选择: 总是选择给定的可无限使用的数中最小的那个，设为。这使得图的规模 ( 个顶点，条边) 最小，从而优化时空复杂度。
无无限物品: 如果所有物品都有限，同余最短路模型不直接适用。需要转为纯粹的多重背包问题。
特殊情况: 如果题目中只有一个数，那么能表示的数就是。如果有一堆数，但其中一个特别小，比如，那所有正整数都能表示出来，问题变得平凡。同余最短路在都相对“正常”大小时最能发挥威力。

2. 处理非互质情况

我们之前大多假设。如果，会发生什么？

可达性: 任何由线性组合出的数，必然是的倍数，因为每个都是的倍数。
模型影响: 在以为模数的图上，我们从源点出发，经过边，边权。由于是的倍数，所以我们能到达的所有顶点的编号都必须是的倍数。
结果: 对于所有，如果，那么将永远是。
解题影响:
- 求最大不可达数: 如果，那么有无穷多个数无法表示（例如所有不是的倍数的数）。这种情况下问题通常会保证互质，或者问法会改变。
- 求区间内可达数: 我们的统计公式依然有效。对于的情况，，贡献为0，这是正确的。只需照常计算即可。

3. 数据范围与溢出

long long 的必要性: 最短路长度可能会很大。的一个粗略上界是。如果和是级别，int 足够。但如果它们更大，或者在混合背包模型中，有限物品的价值或数量很大，那么很容易超过 int 范围。始终使用 long long 存储距离是一个安全的习惯。
INF 的取值: 无穷大 INF 的值需要足够大，要大于任何可能出现的合法路径长度。一个安全的做法是设为这种量级，或者直接设为 1e18。
中间计算: 在区间统计问题中，涉及 (T - d[i]) / m 这样的计算。如果是 long long，要确保整个表达式都以 long long 类型计算，避免中间溢出。

4. Dijkstra 与 SPFA

Dijkstra 的优势: 在同余最短路的基本模型和大多数变种中，边权（即的值）都是正数。因此，使用优先队列优化的 Dijkstra 是最高效和稳妥的选择。其复杂度通常优于 SPFA。
SPFA 的可能性: SPFA 也能解决单源最短路问题。其期望复杂度是，但在特殊构造的图上可以被卡到。在同余最短路的图中，顶点和边分布较为均匀，被卡的风险相对较低。但没有理由不使用更稳定高效的 Dijkstra。
何时必须 SPFA: 只有当模型中出现了负权边时，才必须使用 SPFA。例如，某个特殊操作是“减去一个值”，代价为正，但数值变化为负。这种情况在标准同余模型中极为罕见。

八、写在最后

同余最短路，这个名字完美地概括了它的两个核心要素：同余理论与最短路算法。它为我们提供了一套优雅的范式，用以解决一类关于整数线性组合的计数与最值问题。

其精髓在于降维和转化：

通过选取模数，它将一个在无限整数集上的问题，巧妙地映射到一个只有个状态的有限空间中。每一个状态（顶点）代表一个完整的剩余类。
通过将加法操作定义为图的边，它将寻找“最小可达数”的组合问题，转化为图论中经典的单源最短路问题。

我们从最基础的弗罗贝尼乌斯硬币问题出发，看到了如何构建图、定义最短路的含义，并计算出最大不可达数。接着，我们拓展了模型，解决了区间内可达数的计数问题，展现了模型结果的强大解释力。

更进一步，我们深入探讨了它与背包DP的深刻联系。当面对混合背包问题时，同余最短路可以作为处理无限物品的基石，而有限物品则通过单调队列优化的动态规划过程，对最短路的结果进行高效的迭代更新。这种组合拳式的解法，是处理大规模混合背包问题的利器。

最后，通过分层图的视角，我们理解了如何将额外的约束（如操作次数限制）融入模型，进一步拓宽了其应用边界。

掌握同余最短路，不仅仅是学会一个算法模板。更重要的是理解其背后化无限为有限的数学思想，以及将代数问题图论化的建模技巧。这种思维方式，在算法竞赛的诸多领域，从数论到动态规划，再到计算几何，都无处不在，是通往更高层次解题能力的关键阶梯。

附录：例题选讲

AT_arc084_b Small Multiple

题意概括:
给定一个整数。求一个的正整数倍中，数位之和最小的那个，并输出这个最小的数位和。

解题思路

这个问题可以被看作一个最短路问题。我们想要找到一个目标数，这个数需要满足两个条件：是的倍数，且数位和最小。

状态定义: “是的倍数”这个条件，提示我们用模的余数作为图的状态。我们建立一个有个顶点的图，顶点编号为。
最短路含义: 我们的优化目标是“数位和最小”。因此，我们定义为，所有模余的数中，最小的数位和是多少。我们的最终目标就是。
构建图 (状态转移): 我们如何从一个数得到另一个数？可以考虑两种基本操作来构建任意正整数：
- 乘以10: 如果我们有一个数，我们可以得到。如果，那么。这个操作不改变数位和。因此，这对应一条从顶点到的边，权重为 0。
- 加1: 如果我们有一个数，我们可以得到。如果，那么。这个操作使数位和增加1。这对应一条从顶点到的边，权重为 1。
算法选择: 图中只有权重为0和1的边。这是0-1 BFS的经典应用场景，使用双端队列可以做到线性时间复杂度。
算法流程:
- 初始化距离数组为无穷大。
- 起点是1。因为我们要找正整数倍。数1模余1，数位和为1。所以 d[1]=1。
- 将状态1放入双端队列。
- 循环处理队列，每次从队首取出状态 u。
- 对于 *10 操作，得到新状态 v = (u*10)%K。若 d[v] > d[u]，更新 d[v]=d[u]，并将 v 推入队首。
- 对于 +1 操作，得到新状态 v = (u+1)%K。若 d[v] > d[u]+1，更新 d[v]=d[u]+1，并将 v 推入队尾。
- 算法结束时，d[0] 就是答案。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 100005;
const int INF = 1e9;

int k;
int d[N];

void bfs() {
    for (int i = 0; i < k; ++i) d[i] = INF;
    deque<int> q;

    d[1] = 1; // 从数字1开始, 余数为1, 数位和为1
    q.push_front(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        
        if (u == 0) break; // 找到答案即可提前退出

        // 操作1: 乘以10
        int v1 = (u * 10) % k;
        if (d[v1] > d[u]) {
            d[v1] = d[u];
            q.push_front(v1); // 0花费, 插入队头
        }

        // 操作2: 加1
        int v2 = (u + 1) % k;
        if (d[v2] > d[u] + 1) {
            d[v2] = d[u] + 1;
            q.push_back(v2); // 1花费, 插入队尾
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> k;
    bfs();
    cout << d[0] << endl;
    return 0;
}

代码解释
- d[i] 存储模余的最小数位和。
- 使用 deque 实现0-1 BFS。
- 从状态1开始，因为它代表了最小的正整数。
- *10 转移对应0权边，放入队首；+1 转移对应1权边，放入队尾。
- 最终 d[0] 就是所求的最小数位和。
复杂度分析
- 时间复杂度: 。每个顶点最多进出双端队列一次。
- 空间复杂度: 。用于存储距离数组和双端队列。

P2662 牛场围栏

题意概括:
有种长度为的木料，每种无限。每根木料可以被截短到的任意整数长度。问用这些处理后（或不处理）的木料拼接，无法组成的最大围栏长度是多少。

解题思路

这个问题是弗罗贝尼乌斯硬币问题的一个直接但更复杂的应用。首先，我们需要确定我们拥有的所有“硬币”的面值，即所有可能使用的木料长度。

确定可用长度集合: 对于每一种原始长度为的木料，我们都可以通过截短得到长度为的新木料。我们将所有这些可能的新长度（且为正整数）汇集起来，形成一个大的可用长度集合。
选取模数: 同余最短路的标准做法是选择集合中最小的元素作为模数。我们首先找出集合中最小的正整数，设为。如果原始木料按长度升序排序为，那么最小的可用正长度显然是。
特殊情况: 如果我们计算出的最小可用长度，这意味着我们可以凑出长度为1的围栏。因此，通过重复使用长度1的木料，我们可以凑出任意正整数长度的围栏。在这种情况下，不存在无法修建的最大长度，答案应为-1。
构建模型:
- 我们建立一个有个顶点的图，顶点编号为。
- 的含义是：能凑出的、模余的最小总长度。
- 图的边由集合中的元素（除自身外）确定。对于中每一个不同于的可用长度，它都对应着图中的一组转移：从任意顶点可以到达，代价是增加了长度。这对应着一条从到，权重为的边。
算法流程:
- 首先，生成所有唯一的、正的可用长度，并存入一个集合，同时确定最小可用长度作为模数。
- 以为模数，构建一个同余最短路图。由于需要为每个顶点和每个可用长度添加一条边，图的边数会非常多。
- 一个更高效的实现方式是，在Dijkstra算法的执行过程中动态地考虑这些边。当从优先队列中取出顶点 u 时，我们遍历所有可用长度 j，并尝试用 d[u] + j 来松弛 d[(u+j)%m]。
- 以顶点为源点，d[0]=0，运行Dijkstra算法。
- 算法结束后，如果存在某个仍然是无穷大，说明该余数无法被凑出，这意味着存在无穷多个长度无法修建，答案为-1。
- 否则，所有都是有限值。无法修建的最大长度由弗罗贝尼乌斯数的公式给出：。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3005;
const ll INF = 1e18;

int n;
ll m; // M
ll a[105];
ll d[N];
bool v[N];
vector<ll> ual; // 存储所有唯一可用长度

void dijk(int mod) {
    for (int i = 1; i < mod; ++i) d[i] = INF;
    d[0] = 0;

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [c, u] = pq.top();
        pq.pop();

        if (v[u]) continue;
        v[u] = true;

        // 遍历所有可用长度进行松弛
        for (ll len : ual) {
            if (len == mod) continue; // 模数自身不作为边
            int nxt = (u + len) % mod;
            if (d[nxt] > c + len) {
                d[nxt] = c + len;
                pq.push({d[nxt], nxt});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);

    set<ll> s; // 使用集合自动去重和排序
    for (int i = 0; i < n; ++i) {
        for (ll j = 0; j <= m; ++j) {
            if (a[i] - j > 0) {
                s.insert(a[i] - j);
            }
        }
    }

    if (s.empty() || *s.begin() == 1) { // 如果没有正长度或能凑出1
        cout << -1 << endl;
        return 0;
    }

    int mod = *s.begin(); // 最小可用长度为模数
    for(ll len : s) ual.push_back(len);

    dijk(mod);

    ll ans = 0;
    for (int i = 0; i < mod; ++i) {
        if (d[i] >= INF) { // 存在无法到达的余数
            cout << -1 << endl;
            return 0;
        }
        ans = max(ans, d[i]);
    }
    
    cout << ans - mod << endl;
    
    return 0;
}

代码解释
- 首先读入数据，并将原始木料长度排序。
- 使用 std::set 来高效地生成所有唯一的、正的可用长度。set 的首个元素 *s.begin() 即为最小可用长度。
- 该最小可用长度被选为模数 mod。
- 检查特殊情况：如果集合为空（不可能，因为）或最小可用长度为1，则输出-1。
- dijk 函数实现了Dijkstra算法。与之前模型不同的是，边的信息（所有可用长度ual）是全局的，在每次松弛时遍历使用。
- 主函数在调用 dijk 后，检查是否有无法到达的余数（d[i] == INF），若有则说明 gcd > 1，输出-1。
- 最后，根据公式计算并输出答案。
复杂度分析
- 时间复杂度: 。其中 mod 是最小可用正长度，|ual| 是唯一可用长度的数量。在题目约束下，mod 和 |ual| 均不超过3000，该复杂度可以接受。
- 空间复杂度: 。主要用于存储距离数组和可用长度列表。