#4738. 翻转游戏币(第15届-202308)

翻转游戏币(第15届-202308)

翻转游戏币

题目描述:

桌面上有n枚游戏币,均为反面朝上,编号依次为1到n。有n个人(游戏币的数量与人的数量相等),首先第1个人将所有游戏币翻转,然后第2个人将所有编号是2的倍数的游戏币翻转,接下来第3个人将所有编号是3的倍数的游戏币翻转......以此类推,当最后一个人完成操作后,还有多少枚游戏币正面朝上?

例如:n = 4;

最初4枚游戏币的状态为:反反反反;

经过第1个人翻转后,游戏币的状态为:正正正正;

经过第2个人翻转后,游戏币的状态为:正反正反;

经过第3个人翻转后,游戏币的状态为:正反反反;

经过第4个人翻转后,游戏币的状态为:正反反正;

最后,还有两枚游戏币正面朝上,故答案为2。

输入描述:

输入一个正整数n(3≤n≤109),表示游戏币数量及人的数量

输出描述:

输出一个整数,表示最终游戏币正面朝上的数量

样例输入:

4

样例输出:

2

Limitation

1s, 1024KiB for each test case.