//Dijkstra代码
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define ll long long
int n,k,dis[200005],vis[200005],ans;
vector<int>G[200005];
priority_queue<pair<int,int> >q;
void dijkstra(int s){
    for(int i=0;i<=n;i++)dis[i]=INT_MAX;
    memset(vis,0,sizeof(vis));
    q.push({0,s});
    dis[s]=0;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        vis[u]=1;
        for(auto v:G[u]){
            dis[v]=min(dis[v],dis[u]+1);
            if(!vis[v])q.push({-dis[v],v});
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        G[i].push_back((i+1)%n);
        G[i].push_back((i+k)%n);
    }
    dijkstra(0);
    for(int i=1;i<n;i++)ans=max(ans,dis[i]);
    cout<<ans;
    return 0;
}

MLE记录

//Spfa代码
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
#define ll long long
int n,k,dis[200005],vis[200005],ans;
vector<int>G[200005];
queue<int> q;
void spfa(int s){
	for(int i=1;i<=n;i++)dis[i]=INT_MAX;
	dis[s]=0;
	q.push(s);
	while(q.size()){
		int u=q.front();
        vis[u]=0;
		q.pop();
		for(auto e:G[u]){
			int v=e;
			if(dis[u]+1<dis[v]){
				dis[v]=dis[u]+1;
				if(vis[v]==0){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        G[i].push_back((i+1)%n);
        G[i].push_back((i+k)%n);
    }
    spfa(0);
    for(int i=1;i<n;i++)ans=max(ans,dis[i]);
    cout<<ans;
    return 0;
}

AC记录