#B. 约瑟“人”环

    Type: Default 1000ms 256MiB

约瑟“人”环

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

故事背景

nn 只愚蠢的人类被抓到了土拨鼠浚庭的家中。而这时,浚庭发现他抓的人类数量比它想要的多了一只,于是想将这只幸运的人类吃掉。浚庭觉得,幸运的人类应该味道鲜美,于是就想把这只幸运的人类找到并吃掉。土拨鼠浚庭千思百想,想到了一个找到这只幸运的人类的好方法。

题目描述

首先土拨鼠浚庭将 nn 只愚蠢的人类摆成一个圈。

  • 第一次浚庭要淘汰2个人类, 人类从1号位置开始报数。数到2的人类出列。
  • 第二次浚庭要淘汰3个人类, 人类从刚才出列的人类的下一个位置开始报数,数到3的人类出列。
  • 第三次浚庭要淘汰5个人类, 人类从刚才出列的人类的下一个位置开始报数,数到5的人类出列。
  • 第四次浚庭要淘汰7个人类, 人类从刚才出列的人类的下一个位置开始报数,数到7的人类出列。
  • ……

每次淘汰的人数就是数到几要淘汰的数字。而且这个数字就是前一个数之后的第一个质数。

最后只剩一只愚蠢的人类时,这只人类就是最幸运的土拨鼠,浚庭就要将它吃掉。请你编程计算一下,最幸运的人类站在几号位置。

输入

一个整数 n1n32767n(1\leq n\leq 32767) ,表示土拨鼠的总只数。

输出

最美味的人类的编号。

样例

1
1
11
5

提示

【样例2】说明:

11只人类:

image

第一轮,淘汰2只人类:

image

第二轮,淘汰3只人类:

image

第三轮,淘汰5只人类:

image

因此站在5号位置的人类是最幸运且美味的。

Hello world

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2022-12-2 18:00
End at
2023-1-1 0:00
Duration
702 hour(s)
Host
Partic.
4