约瑟“人”环

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号位置的人类是最幸运且美味的。

菜就多练

Not Attended
Status
Done
Rule
IOI(Strict)
Problem
19
Start at
2024-3-2 19:15
End at
2024-4-13 11:15
Duration
1000 hour(s)
Host
Partic.
3