跳转至

# 同余最短路

当出现形如「给定 𝑛 n 个整数，求这 𝑛 n 个整数能拼凑出多少的其他整数（𝑛 n 个整数可以重复取）」，以及「给定 𝑛 n 个整数，求这 𝑛 n 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 𝐾 K 余 𝑝 p 的数」的问题时可以使用同余最短路的方法．

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的．

类比 差分约束 方法，利用同余构造的这些状态可以看作单源最短路中的点．同余最短路的状态转移通常是这样的 𝑓(𝑖 +𝑦) =𝑓(𝑖) +𝑦 f(i+y)=f(i)+y，类似单源最短路中 𝑓(𝑣) =𝑓(𝑢) +𝑒 𝑑 𝑔 𝑒(𝑢,𝑣)f(v)=f(u)+e d g e(u,v)．

## 例题

### 例题一

P3403 跳楼机

题目大意：给定 𝑥，𝑦，𝑧，ℎ x，y，z，h，对于 𝑘 ∈[1,ℎ]k∈[1,h]，有多少个 𝑘 k 能够满足 𝑎 𝑥 +𝑏 𝑦 +𝑐 𝑧 =𝑘 a x+b y+c z=k．（0 ≤𝑎,𝑏,𝑐 0≤a,b,c，1 ≤𝑥,𝑦,𝑧 ≤1 0 5 1≤x,y,z≤10 5，ℎ ≤2 6 3 −1 h≤2 63−1）

不妨假设 𝑥 <𝑦 <𝑧 x<y<z．

令 𝑑 𝑖 d i 为只通过 操作 2 和 操作 3，需满足 𝑝 m o d 𝑥 =𝑖 p mod x=i 能够达到的最低楼层 𝑝 p，即 操作 2 和 操作 3 操作后能得到的模 𝑥 x 下与 𝑖 i 同余的最小数，用来计算该同余类满足条件的数个数．

可以得到两个状态：

- 𝑖 𝑦→(𝑖 +𝑦)m o d 𝑥 i→y(i+y)mod x

- 𝑖 𝑧→(𝑖 +𝑧)m o d 𝑥 i→z(i+z)mod x

注意通常选取一组 𝑎 𝑖 a i 中最小的那个数对它取模，也就是此处的 𝑥 x，这样可以尽量减小空间复杂度（剩余系最小）．

那么实际上相当于执行了最短路中的建边操作：

`add(i, (i+y) % x, y)`

`add(i, (i+z) % x, z)`

接下来只需要求出 𝑑 0,𝑑 1,𝑑 2,…,𝑑 𝑥−1 d 0,d 1,d 2,…,d x−1，只需要跑一次最短路就可求出相应的 𝑑 𝑖 d i．

基于最短路的实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    #include <iostream>
    #include <queue>

    using namespace std;
    using ll = long long;
    constexpr int MAXN = 100010;
    constexpr ll linf = (1ull << 63) - 1;

    ll h, x, y, z;
    ll head[MAXN << 1], tot;
    ll dis[MAXN], vis[MAXN];
    queue<int> q;

    struct edge {
      ll to, next, w;
    } e[MAXN << 1];

    void add(ll u, ll v, ll w) {
      e[++tot] = edge{v, head[u], w};
      head[u] = tot;
    }

    void spfa() {  // spfa算法，可看最短路部分
      dis[0] = 0;
      vis[0] = 1;
      q.push(0);
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].next) {
          int v = e[i].to, w = e[i].w;
          if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            if (!vis[v]) {
              q.push(v);
              vis[v] = 1;
            }
          }
        }
      }
    }

    int main() {
      cin.tie(nullptr)->sync_with_stdio(false);
      cin >> h;
      cin >> x >> y >> z;
      if (x == 1 || y == 1 || z == 1) {
        cout << h << '\n';
        return 0;
      }
      --h;
      for (int i = 0; i < x; i++) {
        add(i, (i + z) % x, z);
        add(i, (i + y) % x, y);
        dis[i] = linf;
      }
      spfa();
      ll ans = 0;
      for (int i = 0; i < x; i++) {
        if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
      }
      cout << ans << '\n';
      return 0;
    }

但是事实上也不需要进行正常的最短路求解，注意到有两个特殊的性质：

首先，只有两种边权，且对于每一条路径，由于加法交换律，走两种边权的顺序是无影响的．因此可以考虑做两次最短路，每次只建出一类边权的边；

其次，对于只有一类边权的图，每个点 𝑢 u 都有一个入度（来自 (𝑢 −𝑦)m o d 𝑥(u−y)mod x）和一个出度（来自 (𝑢 +𝑦)m o d 𝑥(u+y)mod x），因此整个图必然由若干个环构成．并且可以证明共有 g c d(𝑥,𝑦)gcd(x,y) 个等长的环．

证明

设 𝑑 =g c d(𝑥,𝑦)d=gcd(x,y)，设 𝑥 =𝑑 𝑎,𝑦 =𝑑 𝑏 x=d a,y=d b，有 g c d(𝑎,𝑏) =1 gcd(a,b)=1．

考虑从 𝑢 u 出发走 𝑘 k 步，到达 (𝑢 +𝑘 𝑦)m o d 𝑥(u+k y)mod x．若成环，则 𝑘 𝑦 ≡0(m o d 𝑥)k y≡0(mod x)，即有 𝑘 𝑏 ≡0(m o d 𝑎)k b≡0(mod a)．

由于 g c d(𝑎,𝑏) =1 gcd(a,b)=1，最小的 𝑘 =𝑎 k=a，即环长为 𝑎 =𝑥 𝑑 a=x d．由于是从任意点开始，故每个可能的环长相等，环的数量为 𝑑 d．

并且，边权为正，绕环两圈后，一定不能继续松弛．直接循环更新一遍就行了．这样处理就不会受限于最短路的复杂度，可以做到 𝑂(𝑥)O(x)．

与差分约束问题相同，当存在一组解 {𝑎 1,𝑎 2,⋯,𝑎 𝑛}{a 1,a 2,⋯,a n} 时，{𝑎 1 +𝑑,𝑎 2 +𝑑,⋯,𝑎 𝑛 +𝑑}{a 1+d,a 2+d,⋯,a n+d} 同样为一组解，因此在该题让 𝑖 =1 i=1 作为源点，此时源点处的 𝑑 𝑖 𝑠 1 =1 d i s 1=1 在已知范围内最小，因此得到的也是一组最小的解．

答案即为：

𝑥−1∑𝑖=0(ℎ−𝑑 𝑖 𝑥+1)∑i=0 x−1(h−d i x+1)

加 1 是由于 𝑑 𝑖 d i 所在楼层也算一次．

代码实现上注意到 ℎ h 的范围是 ℎ ≤2 6 3 −1 h≤2 63−1，所以在求解最短路之前 𝑑 𝑖 d i 的初始值应至少设为 2 6 3 2 63，这超过了 C++ 中 `long long` 的最大值．所以可以使用 `unsigned long long` 或者先把 ℎ ←ℎ −1 h←h−1，然后把最低楼层设为 0 0 层，其他代码无异．

基于环优化的实现

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    #include <algorithm>
    #include <climits>
    #include <cstring>
    #include <iostream>
    #include <vector>

    using ll = long long;

    constexpr int maxn = 1e5 + 100;

    ll d[maxn];
    bool vis[maxn];
    ll ans;

    int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

    void upd(int step, int M) {
      int D = gcd(step, M);
      int len = M / D;

      for (int st = 0; st < D; st++) {
        if (vis[st]) continue;
        std::vector<int> v;
        int u = st;
        for (int i = 0; i < len; i++) {
          v.push_back(u);
          vis[u] = true;
          u = (u + step) % M;
        }
        for (int r = 0; r < 2; r++) {
          for (int i = 0; i < len; i++) {
            int las = v[i];
            int now = v[(i + 1) % len];
            if (d[las] != LLONG_MAX) {
              // 如果d[las]=LLONG_MAX，d[las]+step会越界，需要特判
              d[now] = std::min(d[now], d[las] + step);
            }
          }
        }
      }
    }

    int main() {
      ll h;
      std::cin >> h;
      int x[3];
      for (int i = 0; i < 3; i++) {
        std::cin >> x[i];
      }
      std::sort(x, x + 3);
      int M = x[0];

      for (int i = 0; i < M; i++) {
        d[i] = LLONG_MAX;
        // 本题的h达到了ll的上界，如果使用ll的话必需把初值置为LLONG_MAX
      }
      d[0] = 0;

      upd(x[1], M);
      memset(vis, 0, sizeof(vis));
      upd(x[2], M);

      ll H = h - 1;
      ans = 0;
      for (int i = 0; i < M; i++) {
        if (d[i] <= H && d[i] != LLONG_MAX) {
          ans += (H - d[i]) / M + 1;
        }
      }
      printf("%lld\n", ans);
      return 0;
    }

### 例题二

ARC084B Small Multiple

题目大意：给定 𝑛 n，求 𝑛 n 的倍数中，数位和最小的那一个的数位和．（1 ≤𝑛 ≤1 0 5 1≤n≤10 5）

本题可以使用循环卷积优化完全背包在 𝑂(𝑛 l o g 2⁡𝑛)O(n log 2⁡n) 的时间内解决，但我们希望得到线性的算法．

观察到任意一个正整数都可以从 1 1 开始，按照某种顺序执行乘 1 0 10、加 1 1 的操作，最终得到，而其中加 1 1 操作的次数就是这个数的数位和．这提示我们使用最短路．

对于所有 0 ≤𝑘 ≤𝑛 −1 0≤k≤n−1，从 𝑘 k 向 1 0 𝑘 10 k 连边权为 0 0 的边；从 𝑘 k 向 𝑘 +1 k+1 连边权为 1 1 的边．（点的编号均在模 𝑛 n 意义下）

每个 𝑛 n 的倍数在这个图中都对应了 1 1 号点到 0 0 号点的一条路径，求出 1 1 到 0 0 的最短路即可．某些路径不合法（如连续走了 1 0 10 条边权为 1 1 的边），但这些路径产生的答案一定不优，不影响答案．

时间复杂度 𝑂(𝑛)O(n)．

## 习题

洛谷 P3403 跳楼机

洛谷 P2662 牛场围栏

[国家集训队] 墨墨的等式

「NOIP2018」货币系统

AGC057D - Sum Avoidance

「THUPC 2023 初赛」背包

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Enter-tainer, Xeonacid, Jijidawang, R-G-Mocoratioen, TenilTen, CCXXXI, ChungZH, F1shAndCat, kenlig, Menci, ShaoChenHeng, shuzhouliu, Tiphereth-A, XuYueming520, zhangletao
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用