「2018 南京网络预赛」Sum - 线性筛 | Menci's Blog

「2018 南京网络预赛」Sum - 线性筛 | Menci's Blog

定义 $f(x)$ 为满足以下条件的有序二元组 $(a,b)$ 的方案数（即 $(a,b)$ 与 $(b,a)$ 被认为是不同的方案）：

1. $x=ab$；
2. $a$ 和 $b$ 均为无平方因子数（即其因子中没有除 $1$ 以外的完全平方数）。

求 $\sum\limits_{i=1}^nf(i)$，$n\leq 2\times 10^7$。

链接

计蒜客 30999

题解

显然，$f(n)=\sum\limits_{d|n}|\mu(d)\mu(\frac{n}{d})|$ 是积性函数，考虑线性筛。

1. 当 $x$ 为素数时，$f(x)=2$，即 $(1,x)$ 与 $(x,1)$；
2. 当 $x$ 的最小质因子为 $p$，且 时，$f(x)=2f(\frac{p}{x})$；
3. 当 $x$ 的最小质因子为 $p$，且 $p\mid\frac{x}{p}$ 时：
   • 如果 $p|\frac{x}{p^2}$，那么 $x$ 中 $p$ 的指数至少为 $3$，即无论如何划分 $(a,b)$，两个数中一定有一个数中 $p$ 的指数为 $2$，即不存在合法的划分方案。
   • 否则，$x$ 中 $p$ 的指数至少为 $2$，把这两个 $p$ 分别分给 $(a,b)$ 中的 $a$ 和 $b$，剩余的 $\frac{x}{p}$ 就是一个子问题了，即 $f(x)=f(\frac{x}{p^2})$。

Read full article from 「2018 南京网络预赛」Sum - 线性筛 | Menci's Blog