U104531 ⑨baka学数学 #3

⑨baka学会了 [#2](https://www.luogu.com.cn/problem/U104379) 的做法，十分开心，可是当她定睛一看题目，发现她竟然把 $\mu$ 看成了 $\varphi$！ 这下她又不会做了，明明就变了一个符号她怎么就不会做了呢? 因为她是个笨蛋啊！

$\mu(n)=1 $ $(n=1)$ $\mu(n)=(-1)^k$ $(n$ 没有平方数因子，或者说 $n$ 为几个不同质数的积，即 $n=p_1*p_2*...*p_k), p$ 为质数 $\mu(n) =0$ $(n$ 有平方数因子 $)$ $\mu(1$\~$25)$为： ``` 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0 ``` 求 $$ \sum _{i=1}^n\mu(i) $$

一个正整数 $n$

一个整数，答案 > ⑨baka：为啥不用取膜呢？ 你觉得会爆 $longlong$ 么 `^_^`？

$30\%$ 的数据：$1 \le n \le 1000$ $60\%$ 的数据：$1 \le n \le 10^7$ $100\%$ 的数据： $1 \le n \le 10^{10}$ $std$ 在最大的一个点跑了 $1.4s$ ，使用了许多大常数的东西，所以放心做，不用卡常 [题解 Solution](https://www.luogu.com.cn/blog/chinesepikaync/mysolution-9baka-learn-math-3)