(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 莫反

设:

\[ f(x) = \sum_{i=1}^{n} [\max\{d^2, d^2 \mid i\}=x] \] \[ \begin{aligned} F(x) = & \sum_{x \mid d} f(d) \\ = & \sum_{i=1}^n[x^2 \mid i] \\ = & \left\lfloor \frac{n}{x^2} \right\rfloor \end{aligned} \]

答案:

\[ \begin{aligned} f(1) = & \sum_{i=1} \mu(i)F(i) \\ = & \sum_{i=1}^{\lfloor \sqrt{n} \rfloor}\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor \end{aligned} \]

3 公式

根据题意和莫比乌斯函数的定义可以知道题目所求为 \(\sum_{i=1}^n \mu^2(i)\).

有个公式:

\[ \mu^2(n) = \sum_{d^2 \mid n} \mu(d) \]

证明:

\[ \require{extpfeil} \begin{aligned} \mu^2(n) = & [\max\{i, i^2 \mid n\}=1] \\ = & \sum_{d\mid\max\{i\}} \mu(d) \\ \xlongequal{d\mid\max\{i\} \iff d^2 \mid n} & \sum_{d^2\mid n} \mu(d) \\ \end{aligned} \]

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

将公式代入即可:

\[ \begin{aligned} \sum_{i=1}^n \mu^2(i) = & \sum_{i=1}^n \sum_{d^2 \mid n} \mu(d) \\ = & \sum_{d=1}^{\lfloor \sqrt{n} \rfloor} \mu(d)\left\lfloor \frac{n}{d^2} \right\rfloor \end{aligned} \]