(sp4168)Square-free integers

原题链接

使用莫比乌斯函数作为容斥系数.

思路:

答案是$\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)$.

有个公式:

证明:

中间的转换可以由质因数分解得到.

将公式代入即可: