题解 P5438 【【XR-2】记忆】
skydogli
2020-09-05 17:39:17
~~我觉得之前的两篇题解对数论蒟蒻不太友好~~
首先把所有的数拆分成 $a^2b(\mu(b) \ne 0)$ 的形式，不难发现我们会把 $b$ 相同的放在一起，如果对于一种 $b$ 的长度为 $k$，则贡献为 $k-1$，因此答案等于区间长度减去出现的不同的 $b$ 的个数。
然后考虑相对简单的 $l=1$ 的情况，我们发现因为 $l=1$，所以如果 $a^2b(a\ne 1)$ 在区间中，则必有 $b$ 在区间中，也就是说贡献来自有完全平方因子的数，所以答案就是有完全平方因子的数的个数。
这个东西不是很好求，我们改成求不含完全平方因子的数的个数，用区间长度减去它即可。
我们先把它直观的式子写出来：
$$\sum_{i=1}^n [\mu(i)\ne 0]=\sum_{i=1}^n \mu^2(i)$$
然后先给出结论，这个答案是：
$$\sum_{i=1}^n\lfloor\frac{n}{i^2}\rfloor\mu(i)$$
为啥呢，我们把它转化为一个等价的式子：
$$\sum_{i^2j\leq n}$$
我们尝试把 $i^2j$ 的贡献全部放到 $a^2b(\mu(b)\ne 1)$ 上。
不难发现必有 $i|a$ 且 $a$的每个因子都会被枚举到。所以式子就是
$$
\begin{aligned}
\sum_{a^2b\le n,\mu(b)\ne0}\sum_{i|a}\mu(i)&&\\
=\sum_{a^2b\le n,\mu(b)\ne 0}[a=1]&&\\
=\sum_{b=1}^n [\mu(b)\ne0]&&\\
\end{aligned}
$$
于是发现它就等于上面的式子。
所以我们可以 $O(\sqrt{n})$ 预处理， $O(n^{\frac{1}{3}})$ 查询一次这个答案。
然后考虑 $l\ne 1$ 怎么做。我们直接差分的话会多算一些答案，于是考虑如何消除这样的数的贡献。于是我们可以直接枚举$[\frac{l-1}{c^2},\frac{r}{c^2}]$ 包含的区间，然后减去这样的区间中出现的无完全平方因子的个数即可。计算可以小数据查表，大数据$O(n^{\frac{1}{3}})$暴力算。一个毛咕咕的上界是$O(n^\frac{5}{9})$，好像可以更精确一点。
另外要注意不能重复删除贡献，所以区间要合并一下。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MN 10000005
int l,r,p[MN],mu[MN],smu[MN],ssmu[MN],cnt,nn;
bool vis[MN];
void init(int N){
nn=N;
ssmu[1]=smu[1]=1;
for(int i=2;i<=N;++i){
if(!vis[i]){p[++cnt]=i;mu[i]=-1;}
for(int j=1;p[j]*i<=N;++j){
vis[p[j]*i]=1;
if(i%p[j]==0)break;
mu[p[j]*i]=-mu[i];
}
smu[i]=smu[i-1]+mu[i];
ssmu[i]=ssmu[i-1]+(mu[i]!=0);
}
}
int calc(int r){
int ans=r;
if(r<nn)return r-ssmu[r];
int blk=sqrt(r);
for(int i=2,j=0;i*i<=r;i=j+1){
j=min(blk,(int)sqrt(r/(r/i/i)));
ans+=(smu[j]-smu[i-1])*(r/i/i);
assert(i<=j);
}
return r-ans;
}
signed main(){
int l,r;
scanf("%lld%lld",&l,&r);
l--;
init(sqrt(r));
int ans=calc(r)-calc(l);
int lst=l;
for(int i=2;i*i<=r;++i){
int p=l/i/i,q=min(lst,r/i/i);
if(p<q){
ans-=q-calc(q)-p+calc(p);
}
lst=p;
}
printf("%lld\n",ans);
return 0;
}
```