写在卸载之前
一个蒟蒻无力的挣扎
正式开始
【安利一个不错的博客】
我们有一个积性函数\(f(n)\) 现在求
\[\sum_{i=1}^nf(i)\ \ (n≤10^9)
\]
求解积性函数 我们很容易想到线性筛 但是这道题的话只用线性筛过不了
所以 就有了一个叫做杜教筛的东西
根据迪利克雷卷积
\[h=f*g\ \ \ \ \ \ \ \ \ h(n)=\sum_{d|n}g(d)f(\frac{n}{d})
\]
也就是
\[\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}g(d)f(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)
\]
我们令
\[S(n)=\sum_{i=1}^nf(i)
\]
那么
\[\sum_{i=1}^nh(i)=g(1)S(n)+\sum_{d=2}g(i)S(\lfloor\frac{n}{d}\rfloor)
\]
转化一下就是
\[g(1)S(n)=\sum_{i=1}^nh(i)-\sum_{d=2}g(i)S(\lfloor\frac{n}{d}\rfloor)
\]
对于\(S(\lfloor\frac{n}{d}\rfloor)\) 我们可以使用数论分块——递归求解
这样的话\(S(n)\)中的n规模会不断缩小 当缩小到一定规模的时候 就可以使用线性筛了
当然了 对于\(h,g\)我们需要他们是便于做前缀和的数论函数 例如\(h(n)=n,g(n)=n^2,h(n)=n^3\)
具体应用
1.\(\sum_{i=1}^nφ(i)\)
由于
\[\sum_{d|n}φ(d)=n
\]
所以
\[\sum_{i=1}^ni=\sum_{i=1}^n\sum_{d|i}φ(\frac{i}{d})=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}φ(i)=S(n)+\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
\]
由于
\[\sum_{i=1}^ni=\frac{n(n+1)}{2}
\]
也就是
\[S(n)=\frac{n(n+1)}{2}-\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
\]
2.\(\sum_{i=1}^nμ(i)\)
由于
\[\sum_{d|n}μ(d)=[n=1]
\]
所以
\[\sum_{i=1}^n[i=1]=\sum_{i=1}^n\sum_{d|i}μ(\frac{i}{d})=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}μ(i)=S(n)+\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
\]
也就是
\[S(n)=1-\sum_{d=2}^nS(\lfloor\frac{n}{d}\rfloor)
\]
3.\(\sum_{i=1}^niφ(i)\)
我们令
\[Id(n)=n \ \ \ f(n)=nφ(n)
\]
那么
\[f*Id=\sum_{d|n}f(d)Id(\frac{n}{d})=\sum_{d|n}dφ(d)\frac{n}{d}=n\sum_{d|n}φ(d)=n^2
\]
所以
\[\sum_{i=1}^nn^2=\sum_{i=1}^n(f*Id)=\sum_{i=1}^n\sum_{d|i}d\frac{i}{d}φ(\frac{i}{d})=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}iφ(i)=S(n)+\sum_{d=2}dS(\lfloor\frac{n}{d}\rfloor)
\]
由于
\[\sum_{i=1}^nn^2=\frac{n(n+1)(2n+1)}{6}
\]
也就是
\[S(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{d=2}dS(\lfloor\frac{n}{d}\rfloor)
\]
例题
首先是【板子题】
CODE:
#include<bits/stdc++.h>
#define M 10000080
using namespace std;
int T,tot;
long long n;
bool mark[M];
int prime[M],phi[M],mul[M];
long long sum1[M],sum2[M];
map<long long,long long> cdy,wzy;//由于这里存在多组数据的输入输出 所以可能有着重复计算 所以我使用了一个记忆化节省时间
void pre()
{
mul[1]=1;phi[1]=1;
for(int i=2;i<=10000000;++i)
{
if(!mark[i]) {prime[++tot]=i;phi[i]=i-1;mul[i]=-1;}
for(int j=1;j<=tot&&prime[j]*i<=10000000;++j)
{
mark[prime[j]*i]=1;
if(i%prime[j]==0)
{
mul[prime[j]*i]=0;
phi[prime[j]*i]=prime[j]*phi[i];
break;
}
else
{
mul[prime[j]*i]=-mul[i];
phi[prime[j]*i]=(prime[j]-1)*phi[i];
}
}
}
for(int i=1;i<=10000000;++i)
{
sum1[i]=sum1[i-1]+phi[i];
sum2[i]=sum2[i-1]+mul[i];
}
}
long long Phi(long long x)
{
if(x<=10000000) return sum1[x];
if(cdy.count(x)) return cdy[x];
long long tmp=(((long long)(1+x)*(long long)x)>>1);
for(long long l=2,r=0;l<=x;l=r+1)
{
r=x/(x/l);
tmp-=(long long)(r-l+1)*Phi(x/l);
}
return cdy[x]=tmp;
}
long long Mul(long long x)
{
if(x<=10000000) return sum2[x];
if(wzy.count(x)) return wzy[x];
long long tmp=1;
for(long long l=2,r=0;l<=x;l=r+1)
{
r=x/(x/l);
tmp-=(long long)(r-l+1)*Mul(x/l);
}
return wzy[x]=tmp;
}
int main()
{
scanf("%d",&T);pre();cdy.clear();wzy.clear();
while(T--)
{
scanf("%lld",&n);
printf("%lld %lld\n",Phi(n),Mul(n));
}
return 0;
}
然后是具体应用的【简单的数学题】