题意
其实就是给你三个数\(x,y,z\)，问你能够凑出多少个\([1,h]\)之间的数。
\(1\le h \le 2^{63}-1\)，\(1\le x,y,z \le 10^5\)
sol
用\(y,z\)凑出的在模\(x\)意义下相同的数一定是越小越好。
所以可以写一个最短路求出用\(y,z\)凑出的在模\(x\)意义下为\(i\)的最小的数，记为\(f_i\)，那么模意义下为\(i\)的所有数的总贡献就是\[\lfloor\frac{h-f_i}{x}\rfloor+1\ \ \ \ (f_i\le h) \ \ \ \ or\ \ 0\ \ \ \ (f_i>h)\]
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define mk make_pair
const int N = 1e5+5;
int x,y,z,to[N<<1],nxt[N<<1],ww[N<<1],head[N],cnt,vis[N];
ll h,f[N],ans;
priority_queue<pli,vector<pli>,greater<pli> >Q;
void link(int u,int v,int w)
{
to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;
head[u]=cnt;
}
void Dijkstra()
{
memset(f,63,sizeof(f));
f[1%x]=1;Q.push(mk(1,1%x));
while (!Q.empty())
{
int u=Q.top().second;Q.pop();
if (vis[u]) continue;vis[u]=1;
for (int e=head[u];e;e=nxt[e])
if (f[to[e]]>f[u]+ww[e])
f[to[e]]=f[u]+ww[e],Q.push(mk(f[to[e]],to[e]));
}
}
int main()
{
scanf("%lld",&h);
scanf("%d%d%d",&x,&y,&z);
if (y<x) swap(x,y);if (z<x) swap(x,z);
for (int i=0;i<x;++i) link(i,(i+y)%x,y),link(i,(i+z)%x,z);
Dijkstra();
for (int i=0;i<x;++i) if (f[i]<=h) ans+=(h-f[i])/x+1;
printf("%lld\n",ans);
return 0;
}