P11480 [NordicOI 2017] Yule Lads

译自 Nordic Olympiad in Informatics 2017 [Yule Lads](https://noi17.kattis.com/contests/vfoqp8/problems/yule)。

冰岛的孩子们非常幸运。他们有 $N$ 个圣诞老人！这些圣诞老人被称为尤拉兄弟（Yule Lads）。在圣诞节前的 $N$ 个晚上，他们中的一个会来到镇上，给乖孩子送上小礼物，而顽皮的孩子则得到一个土豆。 在冰岛的一个小镇上，有一条街道上有 $N$ 栋房子，编号依次为 $1$ 到 $N$。每栋房子都用圣诞灯装饰得非常漂亮，起初这些灯全都亮着。 在圣诞节前的每个晚上，会有一位尤拉兄弟光临这条街道。圣诞节前第 $K$ 个晚上来访的尤拉兄弟非常喜欢数字 $K$，因此他只会拜访编号可以被 $K$ 整除的房子。此外，尤拉兄弟们很顽皮，会切换每个被拜访房子的圣诞灯的状态（即如果灯亮着则关掉，灯关着则打开）。 然而，有一些尤拉兄弟生病了，没有来到镇上。在圣诞节当天，除了第一栋房子以外，所有房子的灯都亮着。问有多少尤拉兄弟来到了镇上？

第一行输入一个正整数 $N$，表示尤拉兄弟的数量以及街道上的房子数量。

输出一个整数，表示来到镇上的尤拉兄弟的数量。可以假设只有一种可能的情况会导致所有房子的灯亮着，除了第 $1$ 号房子的灯。

考虑 $N=6$ 的情况，街道上有六栋房子，圣诞节前的每个晚上发生以下情况（假设没有尤拉兄弟生病）： - 圣诞节前第 $6$ 天：尤拉兄弟会关闭第 $6$ 号房子的灯。 - 圣诞节前第 $5$ 天：尤拉兄弟会关闭第 $5$ 号房子的灯。 - 圣诞节前第 $4$ 天：尤拉兄弟会关闭第 $4$ 号房子的灯。 - 圣诞节前第 $3$ 天：尤拉兄弟会关闭第 $3$ 号房子的灯，并打开第 $6$ 号房子的灯。 - 圣诞节前第 $2$ 天：尤拉兄弟会关闭第 $2$ 和第 $6$ 号房子的灯，并打开第 $4$ 号房子的灯。 - 圣诞节前第 $1$ 天：尤拉兄弟会关闭第 $1$ 和第 $4$ 号房子的灯，并打开第 $2$、$3$、$5$ 和 $6$ 号房子的灯。 然而，第 $4$ 号房子的灯在圣诞节当天是关闭的，与实际情况不符。 如果只有原本应该在圣诞节前第 $4$ 天到来的尤拉兄弟生病了，那么所有灯都将亮着，除了第 $1$ 号房子的灯。正确答案是 $5$：来到镇上的尤拉兄弟是在第 $6$、$5$、$3$、$2$ 和 $1$ 天。 --- 你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。 | 子任务 | 分数 | 限制条件 | | ------ | ---- | ------------------- | | $1$ | $15$ | $N\leq 13$ | | $2$ | $10$ | $N\leq 1000$ | | $3$ | $12$ | $N\leq 10^5$ | | $4$ | $13$ | $N\leq 5\cdot 10^6$ | | $5$ | $15$ | $N\leq 10^8$ | | $6$ | $14$ | $N\leq 10^{10}$ | | $7$ | $21$ | $N\leq 10^{13}$ |