# 14149: 【原4149】Josephus

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4149

## Sample Input1

``````4 2 1
``````

## Sample Output1

``````2
``````

## Sample Input2

``````4 2 2
``````

## Sample Output2

``````4
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/4/10.
//

#include <iostream>

using namespace std;

using ll=long long;

int main() {
ll n, m, k;
cin >> n >> m >> k;
auto out = new bool[n]{};
ll cur = -1;
while (k--) {
ll mm = m;
while (mm) {
cur = (cur + 1) % n;
while (out[cur]) {
cur = (cur + 1) % n;
}
--mm;
}
out[cur] = true;
}
cout << cur + 1 << endl;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
using namespace std;

constexpr int max_num = 20000000;

bool remain[max_num] = { 0 };

int main() {
long long n, m, k;
cin >> n >> m >> k;

long long cnt = n, cur_pos = 0;
for (; k > 0; --k) {
long long dis = m % cnt;
if (dis == 0)
dis = cnt;
for (long long i = 0; i < dis;) {
++cur_pos;
if (cur_pos > n)
cur_pos = 1;
if (!remain[cur_pos]) {
++i;
}
}
remain[cur_pos] = true;
}

cout << cur_pos;

return 0;
}
``````

## skyzh's solution

``````#include <iostream>
using namespace std;

struct Node {
int x;
Node* next;
Node(int x, Node* next = NULL) : x(x), next(next) {}
};

int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
Node* cur = new Node(i);
ptr->next = cur;
ptr = cur;
}
int cnt_m = 0;
while (true) {
++cnt_m;
if (cnt_m == m) {
prev->next = ptr->next;
--k;
if (k == 0) {
cout << ptr->x << endl;
return 0;
}
cnt_m = 0;
delete ptr;
}
prev = prev->next;
ptr = ptr->next;
}
return 0;
}
``````