(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} \]