• 自己想出来dp，但是求最小 按多少次k这里是暴力的，应该tle了
• 当前dp[i] = min(dp[i-1]+1,x[i])表示，从上一步按一次或者一直按x[i]次+k使得%= i

  #include <iostream>
  #include <algorithm>
  
  using namespace std;
  const int maxn = 1e5+10;
  
  int dp[maxn];
  int N , k;
  int x[maxn];
  void init() {
  	for (int i=1; i<N; i++) {
  		for (int j=1; j<=1e5; j++) {
  			if ( (long long)(j*k) % N == i) {
  				x[i] = j;
  				break;
  			}
  		}
  	}
  }
  int main() {
  	cin >> N >> k;
  	init();
  	
  	dp[0] = 0;
  	for (int i=1; i<N; i++) {
  		dp[i] = min(dp[i-1]+1,x[i] ); 
  	}
  	cout << *max_element(dp,dp+N);
  } 

• bfs
• 将当前点的下面两个点按顺序加入队列中

  #include <iostream>
  #include <queue>
  #include <algorithm>
  
  using namespace std;
  const int maxn = 1e5+10;
  bool vis[maxn];
  int cost[maxn];
  int n,k;
  
  struct node {
  	int x,dist;
  	node () {
  	}
  	node (int a,int b) {
  		x = a;
  		dist = b;
  	}
  };
  void bfs() {
  	queue<node> que;
  	que.push(node(0,0));
  	vis[0] = 1;
  	cost[0] = 0;
  	while (!que.empty()) {
  		node cur = que.front();
  		que.pop();
  
  		int to = (cur.x+1)%n; //先一步一步的走
  		if (!vis[to]) {
  			vis[to] = 1;
  			cost[to] = cur.dist+1;
  			que.push(node(to,cur.dist+1));
  		}
  		to = (cur.x+k)%n;
  		if (!vis[to]) {
  			vis[to] = 1;
  			cost[to] = cur.dist+1;
  			que.push(node(to,cur.dist+1));
  		}
  	}
  	return ;
  }
  
  
  int main() {
  	cin >> n >> k;
  	bfs();
  	cout << *max_element(cost,cost+n);
  	return 0;
  }