自动搬运

查看原文

来自洛谷，原作者为

	wkywkywky 左右两个通电螺线管

搬运于2025-08-24 23:07:10，当前版本为作者最后更新于2024-12-21 18:14:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考考你的注意力。

注意到 $\sum\limits_{i=1}^n 2^{\omega(i)} \equiv 1+\sum\limits_{p\in \mathbb{P},p^k\leq n}2 \pmod 4$。

其中 $\omega(n)$ 为 $n$ 含有不同的素因子的个数。

求出左式后，用筛法筛出 $p\in \mathbb{P},k\leq 2,p\leq n^\frac{1}{k}$ 的个数，就得到 $\pi(n) \bmod 2$ 的结果。

Lemma : $2^{\omega(n)}=\sum\limits_{d|n}\mu^2(d)$

注意到左右两边均为积性函数。

只需证明对 $n=p^k,p\in \mathbb{P}$ 的情况成立。

$2^{\omega(p^k)}=2=\mu^2(1)+\mu^2(p)$

显然成立，引理得证。

$\begin{aligned} \sum\limits_{i=1}^n 2^{\omega(i)} &= \sum\limits_{i=1}^n \sum\limits_{d|i}\mu^2(d) \\ &=\sum\limits_{d=1}^n \mu^2(d)\lfloor \frac{n}{d} \rfloor \\ &=\sum\limits_{d=1}^n (\sum\limits_{k^2|d}\mu(k))\lfloor \frac{n}{d} \rfloor \\ &=\sum\limits_{k=1}^n\mu(k) \sum\limits_{i=1}^{\lfloor \frac{n}{k^2} \rfloor} \lfloor\frac{n}{ik^2}\rfloor \\ &=\sum\limits_{k=1}^n\mu(k) \sum\limits_{i=1}^{\lfloor \frac{n}{k^2} \rfloor} \sigma_{0}(i) \end{aligned}$

对 $\lfloor \frac{n}{k^2} \rfloor$ 整除分块。

对 $\sigma_{0}(n)$ 求和使用 DIVCNT1 的做法。

考虑对 $n\leq V$ 线性筛出 $\sigma_{0}(n)$ 平衡复杂度。

$\frac{n}{k^2}>V \Rightarrow k<\sqrt{\frac{n}{V}}$

$\int_{1}^{(\frac{n}{V})^{1/2}} (\frac{n}{x^2})^{1/3}\ln {\frac{n}{x^2}}\mathrm{d} x=n^{1/2}V^{-1/6}\ln n$

$n^{1/2}V^{-1/6}\ln n=V$

$V=(n^{1/2}\ln n)^{6/7}$

时间复杂度 $O((n^{1/2}\ln n)^{6/7})$。