【算法漫笔004】同余最短路
2026-08-24 14:36:55
发布于：重庆
【算法漫笔004】浅谈同余最短路
突然发现之前写的全部是字符串，于是乎就有了此篇插队在了 Manacher 的前面。
最短路
普通的最短路解决的问题通常是在一个图中寻找两个点之间权值和最短的路径。常见的算法例如 Floyd、Dijkstra、SPFA等都是解决类似问题的算法。而同余最短路解决的问题看似好像和最短路完全不沾边。
同余最短路
考虑以下问题：给定若干正整数 ，求在某个较大的范围 内，有多少个数可以被这些数非负整数线性组合表示（即可重复的选取任意 中的元素），或者求最大不能表示的数。
我们先简化问题，先将区间 改为 解决。但这似乎无法和最短路扯上关系。
的确，这样的问题似乎并不和最短路搭边，那我们能否将问题转化一下呢？
现在设想一下，如果我们选定了某一个数作为 ，比如取 ，那么任何一个能被表示的数 ，显然都可以写成 的形式。
现在，我们将每一个可表示的数 相同的分为一类，称为同余[1]类。比如在 下， 的同余类就包含了 。显然此时每个同余类的元素数量是无限的。因此，对于每个同余类，我们只关心其中最小的可表示数，将其记为 。
如何求得 ？
显然的一种方式是枚举整数 ，从小到大检查 能否被 中的数组合出来。但时间复杂度可以来到 ，效率显然不高。
我们注意到，从任意一个可表示的数 出发，加上任意一个 后仍然可表示。如果我们把余数看作状态，那么从余数 转移到余数 的代价就是 。
有点绕，举个例子。我们取 ，则 。同余类则有 三类。
此时：
若从余数 出发：
- 加 ：，代价
- 加 ：，代价
从余数 出发：
- 加 ：，代价
- 加 ：，代价
从余数 出发：
- 加 ：，代价
- 加 ：，代价
此时我们视代价为边权，构建一个有向图：
以 为源点跑一遍 ，可以得到：
容易发现，。那么求得 后，由于定义，对于每个 都可以表示。所以显然 内可表示的数量为：
总答案即为所有余数的贡献之和：
没有人觉得我Markdown写的很好吗
现在我们解决了 的问题，那么 呢？其实很简单，通过前缀和思想不难得到：。这样我们就轻松的解决了这个问题！
恭喜你，你又可以水一道青题了！
P3403 跳楼机
/*
Code Form
Becoder c2028hf2
ACGO FeIndentOvO
Luogu FeIndent
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int h,dis[N],x,y,z,mod,ans;
bool vis[N];
void SPFA() {
queue<int> q;
memset(dis,0x3f,sizeof dis);
dis[0]=0;
q.push(0);
vis[0]=1;
while (!q.empty()) {
int u=q.front();q.pop();
vis[u]=0;
int v=(u+y)%mod;
if (dis[u]+y<dis[v]) {
dis[v]=dis[u]+y;
if (!vis[v]) q.push(v),vis[v]=1;
}
v=(u+z)%mod;
if (dis[u]+z<dis[v]) {
dis[v]=dis[u]+z;
if (!vis[v]) q.push(v),vis[v]=1;
}
}
}
signed main() {
cin >> h >> x >> y >> z;
mod=x;
SPFA();
for (int i=0;i<mod;i++) {
if (dis[i]<h) {
ans+=(h-dis[i]-1)/mod+1;
}
}
cout << ans;
return 0;
}
注释&致谢
感谢 StackEdit软件，欢迎大家去使用这个免费的 Markdown 编辑软件。它不仅可以在线使用，还可以下载使用。
大家要多多点赞支持啊！这是我更新的动力qwq
同余，即若 且 则 在模 的意义下同余。 ↩︎
有帮助，赞一个