E. 捕梦网

Dreamcatcher

时间限制：1 秒 · 内存限制：1024 MiB

原题：NWERC 2025 D · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

一个圆环上等距分布着 $n$ 个凹槽，沿圆周依次编号为 $1$ 到 $n$ 。你选定一个整数 $k$ ，从凹槽 $1$ 开始，每次沿相同方向前进 $k$ 个凹槽，并用一段直线绳子连接当前凹槽和下一个凹槽；首次回到凹槽 $1$ 时立即停止。

例如， $n = 8$ 、 $k = 3$ 时，连接顺序为 $1 \to 4 \to 7 \to 2 \to 5 \to 8 \to 3 \to 6 \to 1$ 。

请选择 $k$ ，使使用的绳子总长度最大。每段绳子按相应弦的长度计算，即使绳子相交也仍分别计算其长度。最优答案与圆环半径无关。

提示性的几何事实：半径为 $r$ 、圆心角为 $\theta$ 度的弦，其长度为 $2r \cdot \sin(\theta /2)$ 。

输入一个整数 $n$ （ $3 \leq n \leq 10^{9}$ ），表示凹槽数量。

输出一个整数 $k$ （ $1 \leq k < n$ ），使按照上述过程使用的绳子总长度最大。有多个最优答案时输出任意一个即可。

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。