1850年,英格兰教会的一个教区长柯克曼(T. P. Kirkman)提出了一个有趣的女生散步问题。在某女子学校中,15 个女学生同在一个学组。她们每天都要去校外散步。为了加强她们的相互了解,增进友谊,柯克曼设想,如果将女生适当分成 5 组,每组有 3 位女生,使每个女生在 7 天之内,都能够与别的女学生有且仅有一次同组机会。如何分组才能达到此目的?
这个似乎很简单的问题,却有不同寻常的分组算法。这就是后来称为柯克曼三元系的分组算法。过了一百多年,又发明了许多有趣的女生散步分组算法。其中的一个有趣的随机圆环分组算法描述如下。
设有 n 个待分组的女生。首先随机分配给每位女生一个不同的编号。这 n 个女生的编号组成的集合恰为 [1,n]。分在同一组的女生可以自由地在草地上围坐成一个圆圈。圆圈中的每位女生需要满足如下条件,即她的编号和她左右邻座女生编号的乘积均小于 n。当圆圈中只有一个女生时,其自身的编号小于 n。满足上述条件的女生分为一组。其余女生继续按此方法分组。
女生散步问题:对于给定的一个整数 n,计算最多有多少位女生可分在同一组。
输入格式
依次给出待计算的多个测试数据。每行给出由一个整数 n ,表示有 n 个待分组的女生。
输出格式
对于输入文件中的每个测试数据 n,输出这个待分组的女生中,最多有多少位女生可分在同一组,每行输出一个计算结果。
样例数据
样例输入
2
3
5
7
8
样例输出
1
2
2
3
3
子任务
测试点编号 | n |
---|---|
1∼5 | n≤600000 |
6∼8 | n≤50000005 |
9∼10 | n≤1000000000 |
注
- 赛时并未提供数据组数,“请选手自行评估”。
- 题目中的描述存在歧义,但赛时并未给出任何解释。