题解：P14640 【OIMO Round 1】校验

· · 题解

手算一下结论就出来了。但作为一篇题解，还是要严谨证明一下。

思路

首先函数 \lambda(x) = (-1)^{\Omega(x)} 是著名的刘维尔函数，这是一个完全积性函数。它有一个重要结论：

g(n) = \sum_{d|n} \lambda(d) = \begin{cases} 1, & n = k^2 \\ 0, & n \ne k^2 \end{cases}

:::info[证明] 因为 \lambda 是完全积性函数，其狄利克雷卷积 (\lambda * \mathbf{1})(n) = \sum_{d|n} \lambda(d) 的生成函数满足：

\sum_{n=1}^\infty \frac{\lambda(n)}{n^s} = \frac{\zeta(2s)}{\zeta(s)} \quad \Rightarrow \quad \sum_{n=1}^\infty \frac{\sum_{d|n}\lambda(d)}{n^s} = \zeta(s) \cdot \frac{\zeta(2s)}{\zeta(s)} = \zeta(2s)

而 \zeta(2s) = \sum_{n=1}^\infty \frac{1}{n^{2s}} = \sum_{k=1}^\infty \frac{1}{(k^2)^s}，说明只有当 n 是完全平方数时，系数为 1，否则为 0。 ::: 所以 \sum_{i=1}^n g(i) 等于不超过 n 的完全平方数的个数，就是 \lfloor \sqrt{n} \rfloor。

所以题目要求的：

\begin{aligned} & \sum_{i=l}^r \sum_{x \mid i} (-1)^{\Omega(x)} \\ =& \sum_{i=1}^r g(i) - \sum_{i=1}^{l-1} g(i) \\ =& \lfloor \sqrt{r} \rfloor - \lfloor \sqrt{l-1} \rfloor \end{aligned}

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
long long t,l,r,ans;
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&l,&r);
        ans=(int)sqrt(r)-(int)sqrt(l-1);
        printf("%lld\n",ans);
    }
    return 0;
}

:::