QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 6173. 女生散步问题

统计

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 \sim 5$ $n \leq 600\,000$
$6 \sim 8$ $n \leq 50\,000\,005$
$9 \sim 10$ $n \leq 1\,000\,000\,000$

  1. 赛时并未提供数据组数,“请选手自行评估”。
  2. 题目中的描述存在歧义,但赛时并未给出任何解释。