有3种方法

Solution 1 - ordered_set

Utilizing the ordered_set

This data structure is an extension of the general set in C++.

It allows searching for the K-th smallest element in O(log n) time complexity.

#include <iostream> 
using namespace std; 
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
int main() 
{ int n, k;cin >> n >> k;ordered_set os;for (int i = 1; i <= n; i++){os.insert(i);}int cur = 0;for (int i = 1; i <= n; i++){cur = (cur + k) % os.size();auto it = os.find_by_order(cur);cout << *it << " ";os.erase(it);}return 0; 
} 

Solution 2 Blocking Simulation

Assume N is the size of the list, we can divide the numbers into $K\times K$ matrix, where $K=\sqrt{N}$…

这样模拟的时候,做N次循环，循环内枚举为$sqrtN$的常数倍，其中模拟复杂度为$O(N\sqrt{N})$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
void solve()
{int n, k;cin >> n >> k;int m = sqrt(n);vector<vector<int>> g;for (int i = 1; i <= n;){vector<int> tmp;while (tmp.size() < m && i <= n){tmp.push_back(i++);}g.push_back(tmp);}int x = 0, y = 0;for (int i = 0; i < n; i++){int j = k % (n - i);while (j){if (y + j < g[x].size()){y += j;j = 0;}else{j -= g[x].size() - y;y = 0;x = (x + 1) % g.size();}}// 矫正错误位置while (y >= g[x].size()){y = 0;x = (x + 1) % g.size();}cout << g[x][y] << " ";// 最后一个不用删除 避免死循环if (i < n - 1){g[x].erase(g[x].begin() + y);while (y >= g[x].size()){y = 0;x = (x + 1) % g.size();}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t;t = 1;while (t--){solve();}
}

Solution 3 Segment tree

We can generalize this problem into easy range query problem …

Subsequent content will be here soon…,