【洛谷5438】【XR-2】记忆（数论）
题面
题解
很好的一道题目。
我们首先把所有数的每个质因子的出现次数模二，也就是把最大的完全平方因子给除掉。然后剩下部分一样的就可以产生\(1\)的贡献，所以答案就是\(r-l+1\)减去除掉完全平方因子之后不同的数的个数。
那么如果\(l=1\)，答案就是不含完全平方数因子的数的个数，也就是\(\sum_{i=1}^r \mu(i)^2\)，这个可以容斥在\(O(\sqrt r)\)的复杂度下得到答案。
现在我们还是一样的枚举除掉某个完全平方因子之后数的个数，那么对于\(k^2\)而言，除掉之后产生的数是\(\displaystyle (\frac{l-1}{k^2},\frac{r}{k^2}]\)，于是我们要计算的就是区间内不含其他完全平方因子的数的个数。
最后所有区间取个并就可以计算答案了。
对于区间内不含完全平方因子的数的个数，提前预处理出一部分的答案，剩下的部分直接容斥就好了。
复杂度不太会分析。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 10000010
ll l,r,ans;
bool zs[MAX];
int pri[MAX],tot,mu[MAX],smu[MAX],ssmu[MAX];
void Sieve(int n)
{
mu[1]=1;
for(int i=2;i<=n;++i)
{
if(!zs[i])pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=n;++j)
{
zs[i*pri[j]]=true;
if(i%pri[j]==0)break;
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=n;++i)smu[i]=smu[i-1]+mu[i];
for(int i=1;i<=n;++i)ssmu[i]=ssmu[i-1]+(mu[i]!=0);
}
ll Calc(ll n)
{
if(n<MAX)return n-ssmu[n];
ll ret=0,blk=sqrt(n);
for(ll i=2,j;i<=blk;i=j+1)
{
j=min(blk,(ll)sqrt(n/(n/i/i)));
ret-=n/i/i*(smu[j]-smu[i-1]);
}
return ret;
}
int main()
{
scanf("%lld%lld",&l,&r);Sieve(MAX-1);
ans=Calc(r)-Calc(l-1);
for(ll i=2,lst=l-1;i*i<=r;++i)
{
ll L=(l-1)/(i*i),R=min(lst,r/(i*i));
if(L<R)ans-=R-L-Calc(R)+Calc(L);
lst=L;
}
printf("%lld\n",ans);
return 0;
}