New Year and the Sphere Transmission

题目描述

有 $n$ 个人围成一圈坐着，按照座位顺序编号为 $1$ 到 $n$ 。也就是说，对于所有 $i$ 从 $1$ 到 $n-1$ ，编号为 $i$ 和 $i+1$ 的人是相邻的，编号为 $n$ 和 $1$ 的人也是相邻的。

编号为 $1$ 的人一开始手里有一个球。他选择一个不超过 $n$ 的正整数 $k$ ，将球传给他顺时针方向的第 $k$ 个邻居，然后那个人再将球传给他顺时针方向的第 $k$ 个邻居，如此循环，直到编号为 $1$ 的人再次拿到球为止。当他再次拿到球时，球不再被传递。

例如，如果 $n = 6$ 且 $k = 4$ ，球的传递顺序为 $[1, 5, 3, 1]$ 。

考虑所有碰过球的人的编号集合。游戏的乐趣值（fun value）定义为所有碰过球的人的编号之和。在上面的例子中，乐趣值为 $1 + 5 + 3 = 9$ 。

请你找出并输出所有可能的乐趣值的集合，遍历所有可能的正整数 $k$ 。可以证明，在本题的约束下，球总会在有限步内回到编号为 $1$ 的人手中，且对于给定的 $n$ ，可能的乐趣值不超过 $10^5$ 个。

输入仅一行，包含一个整数 $n$ （ $2 \leq n \leq 10^9$ ），表示参与传球的人数。

设所有可能的乐趣值为 $f_1, f_2, \dots, f_m$ 。

输出一行，包含 $m$ 个递增排列的整数 $f_1$ 到 $f_m$ ，用空格分隔。

1 5 9 21

1 10 28 64 136

在第一个样例中，我们已经展示了选择 $k = 4$ 时乐趣值为 $9$ ，选择 $k = 2$ 时也是 $9$ 。选择 $k = 6$ 时乐趣值为 $1$ 。选择 $k = 3$ 时乐趣值为 $5$ ，而 $k = 1$ 或 $k = 5$ 时乐趣值为 $21$ 。

在第二个样例中，乐趣值 $1$ 、 $10$ 、 $28$ 、 $64$ 和 $136$ 分别可以通过 $k = 16$ 、 $8$ 、 $4$ 、 $10$ 和 $11$ 得到。

由 ChatGPT 4.1 翻译