Josephus Problem 1: 逃出生天 - 算法详解及代码实现

约瑟夫问题 1: 逃出生天 - 算法详解及代码实现

题目背景

pzc 从机房中逃了出来，面对他的将是无穷尽的追杀。

题目描述

慌乱间，pzc 闯入了一座魔堡。魔王正筹备着献祭大典，于是把 pzc 绑了起来。

魔王让 pzc 和他的一些奴隶共 'N' 个人围成一个圈，从 '1' 到 'N' 标号，并从第一个开始，隔一个献祭一个人。

如有 '5' 个人，魔王献祭的顺序将是 '2'， '4'， '1'， '5'， '3'。

但是魔王突然心情大好 ~~因为 AK 了 IOI~~，决定放走最后一个留下来的人。

为了活命，pzc 必须立刻找出最后能留下来的那个编号。但是魔王的奴隶实在是太多了 ~~并且 pzc 又太笨~~，所以请你帮忙救出他。

输入格式

第一行一个整数 'N'。

输出格式

输出一行一个整数，表示最后留下来的那个编号。

样例 #1

样例输入 #1

5

样例输出 #1

3

样例 #2

样例输入 #2

10

样例输出 #2

5

提示

对于 '20%' 的数据，'1 <= N <= 1000'。

对于 '50%' 的数据，'1 <= N <= 10^6'。

对于 '70%' 的数据，'1 <= N <= 10^9'。

对于 '100%' 的数据，'1 <= N <= 10^18'。

Test Input Reasoning:

考虑最简单的情况，只有一个人。