题解：

据说是最短路经典题

考虑mod c一意义下

我们会发现mod c相同的话我们一定会用最少步数到达，剩余的都用c转移

由于转移图有环所以我们用spfa来dp（其实也可以理解成最短路）

wa了好多次。。。。初始距离是1不是0。。。。

代码：

#include 
     
      using namespace std;#define rint register ll#define IL inline#define rep(i,h,t) for (rint i=h;i<=t;i++)#define dep(i,t,h) for (rint i=t;i>=h;i--)#define ll long long#define ull unsigned llconst ll N=2e5;ll a,b,c,l,head[N];ull dis[N],n;bool ft[N];const ull INF=1ull<<63;struct re{  ll a,b,c;}e[N*2];void arr(ll x,ll y,ll z){  e[++l].a=head[x];  e[l].b=y;  e[l].c=z;  head[x]=l;}queue
      
        q; int main(){  freopen("1.in","r",stdin);  freopen("1.out","w",stdout);  ios::sync_with_stdio(false);  cin>>n;  cin>>a>>b>>c;  rep(i,0,c) dis[i]=INF;  dis[1]=0;  rep(i,0,c-1)  {    arr(i,(a+i)%c,a);    arr(i,(b+i)%c,b);  }  q.push(1);  while (!q.empty())  {    ll x=q.front(); q.pop();    for (rint u=head[x];u;u=e[u].a)    {      ll v=e[u].b;      if (dis[v]>dis[x]+e[u].c)      {        dis[v]=dis[x]+e[u].c;        if (!ft[v])        {          ft[v]=1;          q.push(v);        }      }    }    ft[x]=0;  }  ull ans=0;  rep(i,0,c-1)  {    dis[i]++;    if (dis[i]<=n)      ans+=(n-dis[i])/c+1;    }  cout<
       
        <