同余最短路是用来解决：形如「给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他整数（\(n\) 个整数可以重复取）」，以及「给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 \(k\) 余 \(p\) 的数」的问题时使用的算法。
核心思想是把无限多个状态压缩到有限个余数里。
先来看模板题：P3403 跳楼机
询问用 \(x,y,z\) 三个数能表示出多少个 \([0,h-1]\) 内的数。\(x,y,z \le 10^5\)，\(h \le 2^{63}-1\)。
显然把所有数的状态都搞出来是不可能的，先考虑只用 \(x\) 这一个数表示。那所有数就都写成了 \(ax+k\) 的形式，那只要我们让 \(by+cz \equiv k (\bmod x)\)，就可以表示余数为 \(k\) 的数了，那么就建立图论模型，\(i\) 号点表示余数为 \(i\) 的数，\(dis_i\) 表示最小的能用 \(y,z\) 表示的同余 \(i\) 的数，我们让 \(i\) 向 \((i+y) \bmod x\) 连边，边权为 \(y\)，\(i\) 向 \((i+z) \bmod x\) 连边，边权为 \(z\)，跑最短路就得到每个 \(dis_i\)。
那么 \(\frac{h-dis_i}{x}+1\)，就是每个同余系的大小了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int h,x,y,z;
const int N = 1e5+10;
struct edge{int v,w;
};
vector<edge>g[N];
int dis[N],vis[N];
void dijkstra(){memset(dis,0x3f,sizeof(dis));pq<pii,vector<pii>,greater<pii> >q;dis[1%x]=1;q.push({1,1%x});while(!q.empty()){int u=q.top().scd,d=q.top().fst;q.pop();if(vis[u])continue;vis[u]=1;for(auto [v,w]:g[u]){if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push({dis[v],v});}}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>h>>x>>y>>z;if(x==1||y==1||z==1){cout<<h<<endl;return 0;}for(int i=0;i<x;i++){g[i].push_back({(i+y)%x,y});g[i].push_back({(i+z)%x,z});}dijkstra();int ans=0;for(int i=0;i<x;i++){if(h>=dis[i])ans+=(h-dis[i])/x+1;}cout<<ans;return 0;
}
例题：ARC084B
从 \(1\) 开始，我们可以通过加一来让数位之和加一，乘十则数位之和不变来表示出所有数。
那么每个余数代表一整个同余系的最小值，只要 \(i\) 向 \((i+1) \bmod k\) 连权值为 \(1\) 的边，\(i\) 向 \((i \times 10) \bmod k\) 连权值为 \(0\) 的边，然后就随便处理了。答案为 \(dis_0\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int k;
const int N = 1e5+10;
struct edge{int v,w;
};
vector<edge>g[N];
int dis[N],vis[N];
void dijkstra(){memset(dis,0x3f,sizeof(dis));pq<pii,vector<pii>,greater<pii> >q;dis[1]=1;q.push({1,1});while(!q.empty()){int u=q.top().scd,d=q.top().fst;q.pop();if(vis[u])continue;vis[u]=1;for(auto [v,w]:g[u]){if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push({dis[v],v});}}}
}
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>k;for(int i=0;i<k;i++){g[i].push_back({(i+1)%k,1});g[i].push_back({(i*10)%k,0});}dijkstra();cout<<dis[0]<<endl;return 0;
}
转圈技巧
观察这个同余最短路的图，我们会发现存在环。我们把这些数看作一个个加入的，假设模数是 \(m\)，当前加入了一个数是 \(x\)，则每一个点 \(i\) 向 \((i+x)\bmod m\) 连边，会形成 \(\gcd(x,m)\) 个环。
证明：形成环就是要从当前节点走若干步之后回到远处，则 \(i+k \times x \equiv i(\bmod m)\)。那 \(k \times x\) 就是 \(m\) 的倍数，而我们要找最小的 \(kx\)，就是 \(lcm(m,x)\)。又因为 \(lcm(m,x)=\frac{m\times x}{\gcd(m,x)}\)，所以环的大小为 \(\frac{m}{\gcd(m,x)}\)，那环的个数就是总点数除以每个环的点数，即 \(\gcd(x,m)\)。
那我们就可以在每个环上更新最短路，可以先绕环一圈找到 \(dis\) 最小的节点，从这个节点出发。也可以直接转两圈，保证每个节点都更新到了。
绕一次环是 \(O(m)\) 的，所以总时间复杂度 \(O(nm)\)，优于 dijkstra 的 \(O(nm \log m)\)。
m=a[1];for(int i=2;i<=n;i++){int x=a[i];int num=__gcd(x,m);for(int j=0;j<num;j++){int p=j;for(int k=0;k<2*m/num;k++){int nx=(p+x)%m;dis[nx]=min(dis[nx],dis[p]+x);p=nx;}}}
P9140 THUPC2023初赛 背包
这个题在可行性的基础上还加入了权值，选择一个数 \(v_i\) 能获得 \(c_i\) 的利益，那么 \(q\) 次询问恰好拼出 \(V\) 的最大利益是多少，不能拼出输出 \(-1\)。\(v_i \le 10^5\)，\(10^{11} \le V \le 10^{12}\)。
因为 \(v\) 很大，我们可以尽可能多的选择性价比最大的物品，即 \(\frac{c_i}{v_i}\) 最大的物品，记其 \(v_i\) 为 \(m\)，\(c_i\) 为 \(w\)。因为只选这种物品可能不能刚好拼出 \(V\)，所以我们要考虑用其他的物品替换掉一部分 \(i\)。设 \(V \bmod m = r\)，那么我们就要去拼出 \(r\) 这个余数，显然有 \(m\) 种。
我们就设 \(f_r\) 表示当余数为 \(r\) 时，其他物品的贡献减去替换掉的 \(i\) 的贡献的最大值。
要令 \(W_总=w \times \lfloor \frac{V-V_{other}}{m} \rfloor + W_{other}\)。因为 \(w \times \lfloor \frac{V}{m} \rfloor\) 是固定的，那么只要考虑后面的 \(W_{other} - w \times \lfloor \frac{V_{other}}{m} \rfloor\)，这就是 \(f_r\) 要维护的式子。
如果新加入了物品 \((v_i,c_i)\)，令 \(d_i=\frac{v_i}{m}\)，那么对它转圈，假设从余数 \(p\) 转移到 \(q\)，则 \(q = (p+v_i) \bmod m\)，如果 \(q \ge m\)，说明我们又替换掉了一整个最佳物品，那 \(d=d_i+1\)，所以转移式为 \(f_q=f_p+c_i-d*w\)。记得 \(f_i (i>0)\) 初值都设为 \(-10^{18}\)，如果最后依然等于此值说明拼不出 \(r\) 这个余数。
对于每个询问，\(r=V \bmod m\)，\(ans = f_r+\frac{V}{m}\times w\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define _int __int128
#define ull unsigned long long
#define pii pair<int,int>
#define fst first
#define scd second
#define pq priority_queue
#define mkp make_pair
#define popcount(x) __builtin_popcount(x)
#define endl '\n'
int n,m,q,w;
const int N = 1e5+10,inf=1e18;
int v[55],c[55],d[55],to[55];
int f[N];
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>q;m=1;for(int i=1;i<=n;i++){cin>>v[i]>>c[i];if(w*v[i]<m*c[i]){w=c[i],m=v[i];}}for(int i=1;i<=n;i++){d[i]=v[i]/m;to[i]=v[i]%m;}for(int i=1;i<m;i++)f[i]=-inf;for(int i=1;i<=n;i++){int num=__gcd(v[i],m);for(int j=0;j<num;j++){int p=j;for(int k=0;k<2*m/num;k++){int q=p+to[i],x=d[i];if(q>=m)q-=m,x++;f[q]=max(f[q],f[p]+c[i]-x*w);p=q;}}}while(q--){int V,ans=0;cin>>V;int p=V%m;ans=f[p]+V/m*w;if(ans<-1e17)cout<<-1<<endl;else cout<<ans<<endl;}return 0;
}