# Nemlit 的博客

By a konjac

### 题解 P3403 【跳楼机】

posted on 2019-04-29 12:10:09 | under 题解 |

## 原文地址

$$dis[(i + y) \% x] = min(dis[(i + y) \% x], dis[i] + y)$$

$$dis[(i + z) \% x] = min(dis[(i + z) \% x], dis[i] + z)$$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define mem(k, p) memset(k, p, sizeof(k))
#define maxn 100005
int n, m, x, y, z, dis[maxn], vis[maxn], ans;
queue<int>q;
il void SPFA() {
mem(dis, 63), q.push(1 % x), dis[1 % x] = 1;
while(!q.empty()) {
int u = q.front(); q.pop(), vis[u] = 0;
int v = (u + y) % x;
if(dis[v] > dis[u] + y) {
dis[v] = dis[u] + y;
if(!vis[v]) vis[v] = 1, q.push(v);
}
v = (u + z) % x;
if(dis[v] > dis[u] + z) {
dis[v] = dis[u] + z;
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
}
signed main() {
SPFA();
rep(i, 0, x - 1) if(dis[i] <= n) ans += (n - dis[i]) / x + 1;
printf("%lld", ans);
return 0;
}