题面
题解
明显地，这个QQ数可以用 \(\mu\) 表示，于是询问就变成了这样：
\[\begin{aligned} & \sum_{i=1}^n\sum_{d|i}\left(1-\mu(d)^2\right)\\ =& \sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor\left(1-\mu(d)^2\right) \end{aligned} \]发现 \(\lfloor\dfrac{n}{d}\rfloor\) 是可以整除分块的，但是 \(n\leq 10^9\) 无法线性筛 \(\mu\)。
考虑如何更快地求出 \(\sum\limits_{i=1}^n\left(1-\mu(d)^2\right)\)，也就是 \(1\sim n\) 中的QQ数个数。
但是有这么一个神奇的式子：
\[\sum_{i=1}^n\left(1-\mu(i)^2\right)=\sum_{x=2}^{\sqrt n}-\mu(x)\lfloor\frac{N}{x^2}\rfloor \]证明：
首先，对于每一个QQ数 \(a\)，他肯定可以拆分成这种形式：\(a=x^2 y\)（其中 \(x\) 不是QQ数），也就是说，我们把每一个QQ数表示成一个非QQ数的平方再乘上一个数。
比如QQ数 \(2^4\times 3^3\times 5\) 可以拆分为 \((2\times 3)^2\times \dots\)（\(x=2\times 3\)）或者 \(2^2\times \dots\)（\(x=2\)）或者 \(3^2\times \dots\)（\(x=3\)）。
那么 \(\sum\limits_{x=2}^{\sqrt n}-\mu(x)\lfloor\dfrac{N}{x^2}\rfloor\) 就可以看成是枚举每一个 \(x\)，然后再枚举有多少个 \(a\)，然后再配上一个 \(-\mu(x)\) 去重。（至于能去重的原因结合 \(\mu\) 的定义以及这个式子想一想：\(\sum\limits_{i=1}^n(-1)^i\dbinom{n}{i}=-1\)）
那么就能在 \(\sqrt n\) 的时间内求出 \(\sum\limits_{i=1}^n\left(1-\mu(d)^2\right)\) 了。
时间复杂度比较玄学，反正能过。
代码如下：
#include<bits/stdc++.h>
#define SN 32000
#define ll long long
using namespace std;
int ql,qr;
int cnt,prime[SN],mu[SN];
bool notprime[SN];
void init()
{
mu[1]=1;
for(int i=2;i<=31622;i++)
{
if(!notprime[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=31622;j++)
{
notprime[i*prime[j]]=1;
if(!(i%prime[j])) break;
mu[i*prime[j]]=-mu[i];
}
}
}
int summu(int n)
{
ll ans=0;
for(int i=2;i*i<=n;i++)
ans-=mu[i]*(n/i/i);
return ans;
}
ll solve(int n)
{
ll ans=0;
for(int l=1,r,last=0;l<=n;l=r+1)
{
r=n/(n/l);
ll tmp=summu(r);
ans+=(n/l)*(tmp-last);
last=tmp;
}
return ans;
}
int main()
{
init();
scanf("%d%d",&ql,&qr);
printf("%lld\n",solve(qr)-solve(ql-1));
return 0;
}