题目描述
Srwudi的家是一幢h层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi改造了一个跳楼机，使得访客可以更方便的上楼。

经过改造，srwudi的跳楼机可以采用以下四种方式移动：

向上移动x层；

向上移动y层；

向上移动z层；

回到第一层。

一个月黑风高的大中午，DJL来到了srwudi的家，现在他在srwudi家的第一层，碰巧跳楼机也在第一层。DJL想知道，他可以乘坐跳楼机前往的楼层数。

输入格式
第一行一个整数h，表示摩天大楼的层数。

第二行三个正整数，分别表示题目中的x, y, z。

输出格式
一行一个整数，表示DJL可以到达的楼层数。

输入输出样例
输入 #1复制
15
4 7 9

输出 #1复制
9

输入 #2复制
33333333333
99005 99002 100000

输出 #2复制
33302114671

同余最短路。

我们考虑d[i]的含义为，能到达的 mod x == i的最小楼层。并且只用操作2和操作3.

然后对于每一个都能加上 k倍的x。

所以答案就为：ans+=(h−d[i])/x+1;

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int h,x,y,z,res,d[N];
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
void spfa(){
	memset(d,0x3f,sizeof d); queue<int> q;	int vis[N]={0};
	d[1]=1; q.push(1); vis[1]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				if(!vis[to[i]])	vis[to[i]]=1,q.push(to[i]);
			}
		}
	}
}
signed main(){
	cin>>h>>x>>y>>z;
	if(x==1||y==1||z==1)	return printf("%lld\n",h),0;
	for(int i=0;i<x;i++)	add(i,(i+y)%x,y),add(i,(i+z)%x,z);
	spfa();
	for(int i=0;i<x;i++)	if(d[i]<=h)	res+=(h-d[i])/x+1;
	cout<<res<<endl;
	return 0;
}