题目描述

wzazzy先将天上n个星星排成一排，起初它们都是暗的。

他将挥动n次魔法棒，第i次挥动会将编号为i的正整数倍的星星的亮暗反转，即亮的星星转暗，暗的星星转亮。

wzazzy想问，最终会有多少个星星依旧闪亮在天空。

输入

一个整数n，含义请见题目描述。1<=n<=1e18

输出

一个整数ans，即n次操作后会有多少个星星依旧闪亮。

样例

输入 Copy 3 输出 Copy 1

题解

首先，我们来观察一下挥动魔法棒的过程，将其抽象为对一个长度为 $n$ 的二进制串的操作。比如当 $n=6$ 时，第一次挥动魔法棒相当于将二进制串中所有以 $1$ 结尾的位置取反，即 $110 \Rightarrow 100$；第二次挥动魔法棒相当于将所有以 $10$ 结尾的位置取反，即 $100 \Rightarrow 101$；第三次挥动魔法棒相当于将所有以 $11$ 结尾的位置取反，即 $101 \Rightarrow 001$。

那么，对于一个二进制位 $i$，如果它被挥动了奇数次魔法棒，那么最终它就会变成和 $1$ 不同的数，也就是说它最终的亮暗状态会发生改变；反之，如果它被挥动了偶数次魔法棒，那么最终它的亮暗状态不会改变。

考虑对于某个正整数 $d$，它会被哪些数挥动魔法棒。因为 $d$ 的倍数就是以 $d$ 结尾的数，所以一个以 $d$ 结尾的数会在第 $d$ 次、第 $2d$ 次、第 $3d$ 次……挥动魔法棒。也就是说，如果 $d$ 的因子个数为奇数，那么 $d$ 最终的亮暗状态会发生改变；否则，$d$ 最终的亮暗状态不会改变。

因此，我们只需要求出 $1$ 到 $n$ 中因子个数为奇数的正整数个数即可。对于一个正整数 $d$，它的因子个数为奇数当且仅当它是一个完全平方数，因为对于任意正整数 $n$，如果 $n$ 可以分解成质因数的幂的乘积 $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$，那么它的因子个数就是 $(a_1+1)(a_2+1)\cdots(a_k+1)$，因此只有当所有指数都为偶数时这个值才为奇数。

因此，我们可以通过求 $1$ 到 $n$ 中完全平方数的个数来得到因子个数为奇数的正整数个数。完全平方数的个数平均每 $2\sqrt{n}$ 个数中才会有一个，所以 $1$ 到 $n$ 中完全平方数的个数大概就是 $\sqrt{n}/2$，因此最终的答案就是 $\lfloor \sqrt{n} \rfloor$。注意在 C 语言中需要使用 long long 类型来存储较大的整数。

代码

完整的 C 语言程序如下：

#include <stdio.h>
typedef long long ll;
int main() {
    ll n;
    scanf("%lld", &n);
    printf("%lld\n", (ll) (sqrt(n)));
    return 0;
}