使用莫比乌斯函数作为容斥系数.
思路:
答案是$\sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{i^2} \right\rfloor \mu(i)$, 直接计算即可, 也可以使用数论分块加速.
有三个方法来解释这个答案:
1 容斥
无平方因子数的个数较难计算, 可以先计算有平方因子数的个数.
枚举每个平方数, 计算平方数的倍数的个数, 则有$\sum_{i=2}^{\lfloor \sqrt{n} \rfloor} \left\lfloor \frac{n}{i^2} \right\rfloor$.
此时肯定有重复, 于是需要乘上容斥系数$\color{red}{\mu(i)}$.
$\mu(i)$在此处可以如此解释: 将每个数质因数分解, 若其中某个质因数的幂次大于等于2则将该数放入与这个质因数有关的集合中, 然后进行容斥.
然后考虑系数的正负即可得到答案.
2 莫反
设:
答案:
3 公式
根据题意和莫比乌斯函数的定义可以知道题目所求为$\sum_{i=1}^n \mu^2(i)$.
有个公式:
证明:
中间的转换可以由质因数分解得到.
将公式代入即可: