Problem J26: The Jail Keeper's Problem / 狱吏问题

版权信息： · 数学建模与因数分析枚举问题

任务总览

题目描述

国王下令赦免部分囚犯。规则如下：

• 有 $n$ 间牢房，初始​ 全部门锁关闭 ​；
• 狱吏从第 1 次到第 $n$ 次，共走过牢房 $n$ 遍；
• 第 $k$ 次经过牢房时，他会 ​ 从第 $k$ 间开始，每隔 $k$ 间转动一次门锁 ​；
• 每次转动会使门锁的状态反转（开变关，关变开）；
• 最终，​ 门开着的牢房编号对应的犯人可被释放 ​。

请你编程，找出哪些牢房最后门是开着的。

输入格式

一行一个正整数 $n$（$1 \leq n \leq 1, 000, 000$），表示牢房数量。

输出格式

输出所有门为打开状态的牢房编号，编号按从小到大排列，用空格分隔。

输入输出样例

输入示例

15

输出示例

1 4 9

题目分析与解法

观察转动规则：

• 第 $k$ 次会影响所有编号是 $k$ 的倍数的牢房；
• 每个牢房 $i$ 被转动的次数等于 $i$ 的因子个数；
• 如果一个数的因子个数是奇数，它最终是​ 打开的 ​；
• ​ 只有完全平方数有奇数个因子 ​（如 $1, 4, 9, 16, \dots$）；

因此：

✅ 最后门为开着的牢房编号即为所有 $i ^ 2 \leq n$ 的 $i ^ 2$。

时间复杂度分析