题目描述
求 \(S_1(n)=\displaystyle\sum_{i=1}^{n}\varphi(i)\) 和 \(S_2(n)=\displaystyle\sum\limits_{i=1}^{n}\mu(i)\) 的值，\(T\leq 10,n<2^{31}-1\)。
杜教筛
在莫比乌斯反演的题目中，往往要求出一些数论函数的前缀和，利用 杜教筛 可以在低于线性时间的复杂度内求出这些前缀和。
对于数论函数 \(h=f\ast g\)，要求我们计算 \(\displaystyle\sum\limits_{i=1}^{n}h(i)\)。
记 \(S(n)=\displaystyle\sum_{i=1}^{n}f(i)\)。
想办法构造一个 \(S(n)\) 关于 \(S(\lfloor\frac{n}{i}\rfloor)\) 的递推式。
\[\sum\limits_{i=1}^{n}h(i)=\sum\limits_{i=1}^{n}\sum_{d|i}f(d)·g(\frac{i}{d})=\sum\limits_{d=1}^{n}g(d)·\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)=\sum\limits_{d=1}^{n}g(d)·S\Big(\Big\lfloor\frac{n}{d}\Big\rfloor\Big) \]证明：
\(f(d)g(\frac{i}{d})\) 就是对所有 \(i\leq n\) 算贡献，因此变换枚举顺序，枚举 \(d,\frac{i}{d}\)（分别对应新的 \(i,j\)）。
\[\begin{aligned}&\displaystyle\sum\limits_{i=1}^{n}\sum\limits_{d|i}f(d)g(\frac{i}{d})\\=&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(i)f(j)\\=&\sum\limits_{i=1}^{n}g(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)\\=&\sum\limits_{i=1}^{n}g(i)S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big) \end{aligned} \]可以得到递推式：
\[S(n)=g(1)S(n)=\sum\limits_{i=1}^{n}(f\ast g)(i)-\sum\limits_{i=2}^{n}g(i)S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big) \]假如我们可以快速对 \(\displaystyle\sum\limits_{i=1}^{n}(f\ast g)(i)\) 求和，并用数论分块求解 \(\displaystyle\sum\limits_{i=2}^{n}g(i)S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)\) 就可以在较短时间内求得 \(g(1)S(n)\)。
莫比乌斯函数前缀和
由狄利克雷卷积，我们知道：
\[\epsilon=\mu\ast I\Longleftrightarrow\epsilon(n)=[n=1]\Longleftrightarrow\epsilon(n)=\sum\limits_{d|n}\mu(d)\\S_2(n)=\sum\limits_{i=1}^{n}\epsilon(i)-\sum\limits_{i=2}^{n}S_1\big(\big\lfloor\frac{n}{i}\big\rfloor\big) \]由于 \(\lfloor\frac{n}{i}\rfloor\) 最多只有 \(O(\sqrt{n})\) 种取值，可以用数论分块来计算每一项的值。
直接计算的时间复杂度为 \(O(n^{\frac{3}{4}})\)。考虑先线性筛预处理出前 \(n^{\frac{2}{3}}\) 项，剩余部分的时间复杂度为 \(O\Big(\displaystyle\int_{0}^{n^{\frac{1}{3}}}\sqrt{\frac{n}{x}}dx\Big)=O(n^{\frac{2}{3}})\)。
对于较大的值，需要用 \(\text{map}\) 存下其对应的值，方便以后使用时直接使用之前计算的结果。
欧拉函数前缀和
使用杜教筛求解
记 \(S_1(i)=\displaystyle\sum\limits_{i=1}^{n}\varphi(i)\)。
由于 \(\varphi \ast I=\mathbf{id}\)，所以：
\[\displaystyle\sum\limits_{i=1}^{n}(\varphi\ast I)(i)=\sum\limits_{i=1}^{n}I(i)· S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)\\\sum\limits_{i=1}^{n}\mathbf{id}(i)=\sum\limits_{i=1}^{n}I(i)·S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)\\\frac{n(n+1)}{2}=\sum\limits_{i=1}^{n}S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)\\S_1(n)=\sum_{i=1}^{n}\mathbf{id}(i)-\sum\limits_{i=2}^{n}I(i)S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big)=\frac{n(n+1)}{2}-\sum\limits_{i=2}^{n}S\Big(\Big\lfloor\frac{n}{i}\Big\rfloor\Big) \]使用莫比乌斯反演求解
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1]=\sum\limits_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor^{2} \]由于题目所求的是 \(\displaystyle\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}1·[\gcd(i,j)=1]\)，所以我们排除掉 \(i=1,j=1\) 的情况，并将结果除以 \(2\) 即可。
观察到，只需求出莫比乌斯函数的前缀和，就可以快速计算出欧拉函数的前缀和了。时间复杂度 \(O(n^{\frac{2}{3}})\) 。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2000010;//n^(2/3)
bool vis[N];
long long n,prime[N+10],mu[N+10],sum[N+10],cnt;
map<long long,long long> mp;
long long S_mu(long long n)
{
if(n<N)
return sum[n];
if(mp[n])
return mp[n];
long long ans=1;
for(long long l=2,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=ans-S_mu(n/l)*(r-l+1);
}
mp[n]=ans;
return ans;
}
long long S_phi(long long n)
{
long long ans=0;
for(long long l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=ans+(S_mu(r)-S_mu(l-1))*(n/l)*(n/l);
}
return (ans-1)/2+1;
}
void init()
{
mu[1]=1;
for(int i=2;i<=N;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
else
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=N;i++)
sum[i]=sum[i-1]+mu[i];
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
scanf("%lld",&n);
printf("%lld %lld\n",S_phi(n),S_mu(n));
}
return 0;
}