P14640 【OIMO Round 1】校验 题解

· · 题解

把 n 质因子分解：

n = \prod _ {i = 1} ^ {s} p _ i ^ {k _ i}

由于

\begin{aligned} \sum _ {x \mid i} (-1) ^ {\Omega(x)} &= \sum _ {j _ 1 = 0} ^ {k _ 1} \sum _ {j _ 2 = 0} ^ {k _ 2} \cdots \sum _ {j _ s = 0} ^ {k _ s} (-1) ^ {j _ 1 + j _ 2 + \cdots + j _ s} \\ &= \prod _ {i = 1} ^ s \left( \sum _ {j = 0} ^ {k _ i} (-1) ^ j \right) \\ &= \prod _ {i = 1} ^ s v(k _ i) \end{aligned}

若 n 不是完全平方数，则必存在至少一个奇数 k _i，此时 v(k _ i) = 0 因而整个乘积就是 0。只有 n 是完全平方数时，k _ i 全是偶数，v(k _ i) 全是 1，因而整个乘积式即为 1。

所以

\begin{aligned} \sum _ {i = l} ^ r\sum _ {x \mid i} (-1) ^ {\Omega(x)} &= \sum _ {x = l} ^ r \left[\sqrt{x} \in \Z\right] \\ &= \left\lfloor\sqrt{r}\right\rfloor - \left\lfloor\sqrt{l - 1}\right\rfloor \end{aligned}

因而也就可以 \mathcal{O}(1) 计算。