U379712 开关问题

假设 $n=100$ ，并且结果是要你输出最后处于打开状态的开关标号（不妨模拟一下看看这里的输出有什么规律并且自己思考一下为什么有这个规律）。

有一排 $n$ 个开关，初始时，均处于关闭状态，现在按 $i=1,2,...,n$ 的顺序执行共 $n$ 次操作：第 $i$ 次操作时，翻转第 $i$ 个、第 $2i$ 个、...、第 $⌊n/i⌋×i$ 个开关，即，把打开的关闭，把关闭的打开。问：最终处于关闭状态的开关有几个？ （说明：对于实数 $r$ ，符号$⌊r⌋$ 表示不超过 $r$ 的最大整数，俗称“向下取整”）

一行一个正整数 $n(1≤n≤10^8)$。

一行一个正整数表示最终处于关闭状态的开关数量。

对于样例 $n=6$，初始时第 $1$~$n$ 个开关状态分别为0,0,0,0,0,0，执行操作如下： 翻转第 $1$ 个、第 $2$ 个、...、第 $6$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,1,1,1,1,1； 翻转第 $2$ 个、第 $4$ 个、第 $6$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,0,1,0,1,0； 翻转第 $3$ 个、第 $6$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,0,0,0,1,1； 翻转第 $4$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,0,0,1,1,1； 翻转第 $5$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,0,0,1,0,1； 翻转第 $6$ 个开关，此时第 $1$~$n$ 个开关状态分别为1,0,0,1,0,0。 因此最终有四个开关处于关闭状态，答案为 $4$。