同余最短路可以解决形如「给定 (n) 个整数，求这 (n) 个整数能拼凑出多少的其他整数（可以重复取整数）」「给定 (n) 个整数，求这 (n) 个整数不能拼凑出的最小（最大）的整数」的问题 .
1. 跳楼机
给定 (x,y,z,h)，问有多少个 (kin[1,h]) 使得 (k=px+qy+rz)，其中 (p,q,r) 是变量 .
不妨设 (x<y<z) .
令 (d_i) 表示最小的满足条件且 (kequiv ipmod x) 的 (k) .
考虑将 (q,r) 加一（将 (p) 加一对 (d_i) 没有贡献），可以发现：
发现这与最短路中的 (dis_v=dis_u+val_{u,v}) 类似，所以对于每个 (iin[0,x)) 建一个点，将 (i o (i+y)mod x) 连一条边权为 (y) 的边，将 (i o (i+z)mod x) 连一条边权为 (z) 的边，然后跑一边最短路即可求出所有 (d_i) .
不难发现，对于 (d_ile h)，每个 (d_i) 其答案的贡献为 (leftlfloordfrac{h-d_i}x ight floor+1)（(+1) 是因为自己也算一个），从而，答案为：
时间复杂度 (O(x))（当然这里是 (x<y<z) 前提下的，一般的，时间复杂度是 (O(min{x,y,z}))）
Code:
using namespace std;
const int N=1e5+500;
typedef unsigned long long ull;
typedef long long ll;
ll x,y,z,h,dis[N];
bool vis[N];
typedef vector<pair<ll,ll> > graph[N];
graph g;
inline void addedge(ll u,ll v,ll w){g[u].push_back(make_pair(v,w));}
struct node
{
int idx; ll dis;
node(int _=0,ll __=0){idx=_; dis=__;}
bool operator <(const node& u)const{return dis>u.dis;}
};
void dijkstra(int s) // spfa 爬，dijkstra 天下第一
{
memset(dis,0x3f,sizeof dis); memset(vis,false,sizeof vis);
priority_queue<node> q; q.push(node(s,0)); dis[s]=0;
while (!q.empty())
{
node now=q.top(); q.pop(); int u=now.idx,S=g[u].size();
if (vis[u]) continue;
vis[u]=true;
for (int i=0;i<S;i++)
{
int v=g[u][i].first,w=g[u][i].second;
if (dis[u]+w<dis[v]){dis[v]=dis[u]+w; if (!vis[v]) q.push(node(v,dis[v]));}
}
}
}
int main()
{
scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
if ((x==1)||(y==1)||(z==1)){printf("%lld",h); return 0;} // 假设 x<y<z，若 x=1，则令 q=r=0，从而 k 可以取到 [1,h] 中所有数
if (x>y) swap(x,y); // 这六句仅仅是为了让 x<y<z
if (y>z) swap(y,z);
if (x>z) swap(x,z);
if (x>y) swap(x,y);
if (y>z) swap(y,z);
if (x>z) swap(x,z);
for (int i=0;i<x;i++) addedge(i,(i+y)%x,y),addedge(i,(i+z)%x,z);
dijkstra(0); ll ans=0;
for (int i=0;i<x;i++)
if (h>=dis[i]) ans+=(h-dis[i]-1)/x+1; // 注意这里初始楼层是 1 所以每个 d[i] 都要 +1
printf("%lld",ans);
return 0;
}
仅在此题给出代码 .
2. 墨墨的等式
给定 (a_{1cdots n},l,r)，问有多少个 (kin[l,r]) 使得 (k=sumlimits_{i=1}^na_it_i)，其中 (t_{1cdots n}) 是变量 .
上一题的拓展，上一题是 (l=1,n=3) 的特殊情况，这个一般的情况类似 .
时间复杂度 (O(nminlimits_i{a_i}))
3. 很多序列
给定 (n) 个递增正整数 (x_{1cdots n})，求不能由这些数字线性组合表示出的最大正整数 .
(1<n<6)，(x_1le 10^{6-n})，(x_2ge 10^{11+n})，(x_nle 10^{12+n})，(gcd(x_1,x_2)=1) .
如果 (n=2)，那么就是小凯的疑惑，答案就是 (x_1x_2-x_1-x_2) .
类似的，把 (i) 向 ((i+x_i)mod x_1) 连边权为 (x_i) 的边，跑一边最短路，假设最短路是 (d_{1cdots n}) 答案就是
4. 牛场围栏
给定序列 (l_{1cdots n})，每个 (l_i) 可以减少至多 (m)，问无法表示为 (l_{1cdots n}) 的线性组合的最大数 .
和上一题类似 .
5. 货币系统
问题 (3) 的拓展，两种货币系统等价，当且仅当两种货币系统的 (d) 数组完全相同，开一个新数组记录转移用到的币值，并且要求币值尽量小 .
最后统计一下币值数目即可 .
6. 巡回
给定一个 (n) 个点 (m) 条边的无向图，问有没有 (1) 到 (n) 长度为 (t) 的路径 .
(1le n,mle 50)，(1le tle 10^{18})，(1le 边权le 10^4)
任选一条边 ((u,n,w))，注意到，如果有一条长度为 (d) 的路径，也必然会有长度为 (d+2w) 的路径，故考虑在 (mod 2w) 意义下做同余最短路 .
令 (d_{u,k}) 表示满足存在一条从 (1) 到 (u) 长度为 (i) 的路径且 (kequiv ipmod{2w}) 的最小的 (i)，转移用最短路算法实现即可 .
答案就是 ([d_{n,Tmod 2w}le T]) .
注意若不存在从 (1) 到 (n) 的路径，那么也是不存在这样的路径的 .