我们能发现这个东西是以2 – k的lcm作为一个循环节， 然后bfs就好啦。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long longusing namespace std;const int N = 5e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-);LL a, b;
int k, lcm = ;
int dp[N];void getDp(int x) {
memset(dp, -, sizeof(dp));
dp[x] = ;
queue<int> que;
que.push(x);
while(!que.empty()) {
int u = que.front(); que.pop();
if(dp[u - ] == -) {
dp[u - ] = dp[u] + ;
que.push(u - );
}
for(int i = ; i <= k; i++) {
int v = u - (u % i);
if(~dp[v]) continue;
dp[v] = dp[u] + ;
que.push(v);
}
}
}int main() {
scanf("%lld%lld%d", &a, &b, &k);
swap(a, b);
for(int i = ; i <= k; i++)
lcm = lcm / __gcd(lcm, i) * i;
LL ans = ;
LL R = b - (b % lcm);
LL L = a + (lcm - a % lcm) % lcm;
if(L <= R) {
LL cnt = (R - L) / lcm;
getDp(lcm - );
ans = dp[] * cnt + cnt;
if(a % lcm) ans += dp[a % lcm] + ;
getDp(b % lcm);
ans += dp[];
} else {
getDp(b % lcm);
ans = dp[a % lcm];
}
printf("%lld\n", ans);
return ;
}/*
*/
