P11419

· · 题解

考考你的注意力。

注意到 \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)

显然成立，引理得证。

\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})。