积性函数：
定义
设f(n)为积性函数,n=ab且(a,b)=1，有f(n)=f(a)*f(b)
完全积性函数
n=ab，即有f(n)=f(a)*f(b)，不要求(a,b)=1;
常见函数
\(\epsilon,\phi,d,\sigma,I,\mu,Id\)
迪利克雷卷积
定义
一种数论意义上的卷积，\((f*g)(n)=\sum_{d|n}f(d)*g(n/d)\)
性质
交换律，结合律，分配律。
积性函数的卷积仍为积性函数，但完全积性函数的卷积不一定是完全积性。
莫比乌斯反演
\(\epsilon=I*\mu,\phi=Id*\mu,d=I*I,\sigma=I*Id\)
前两个尤为重要。
常用技巧
找\(\sum\limits_{1<=i<=n,1<=j<=m}f((i,j))=\sum\limits_{d=1}^{min(n,m)}g(d)\lfloor {n/d}\rfloor \lfloor {m/d}\rfloor\)
几道例题
要点
\(\epsilon=I*\mu\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
void read(T &x){
x=0;T fl=1;char tmp=getchar();
while(tmp<'0'||tmp>'9')fl=tmp=='-'?-fl:fl,tmp=getchar();
while(tmp>='0'&&tmp<='9')x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
x*=fl;
}
const int maxn=1e7+100;
int p[maxn],pr[maxn];
int cnt;
int mu[maxn];
ll sum[maxn];
int n,m;
void solve(){
p[1]=1,mu[1]=1;
for(int i=2;i<maxn;i++){
if(!p[i])mu[i]=-1,p[i]=i,pr[++cnt]=i;
for(int j=1;j<=cnt&&pr[j]*i<maxn;j++){
p[i*pr[j]]=pr[j];
if(p[i]==pr[j]){
mu[i*pr[j]]=0;
break;
}
else mu[i*pr[j]]=-mu[i];
}
}
for(int i=1;i<maxn;i++)
sum[i]=sum[i-1]+mu[i];
}
signed main(){
solve();
int T;cin>>T;
while(T--){
cin>>n>>m;
if(n>m)swap(n,m);
ll ans=0;
for(int l=1;l<=n;l++){
int r=min(n/(n/l),m/(m/l));
ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
l=r;
}
cout<<ans<<endl;
}
return 0;
}
要点
与上题同理，
\(Id=I*\phi\)
变量名应该是phi，偷懒没改。。。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
void read(T &x){
x=0;T fl=1;char tmp=getchar();
while(tmp<'0'||tmp>'9')fl=tmp=='-'?-fl:fl,tmp=getchar();
while(tmp>='0'&&tmp<='9')x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
x*=fl;
}
const int maxn=1e7+100;
int p[maxn],pr[maxn];
int cnt;
int mu[maxn];
ll sum[maxn];
int n,m;
void solve(){
p[1]=1,mu[1]=1;
for(int i=2;i<maxn;i++){
if(!p[i])mu[i]=i-1,p[i]=i,pr[++cnt]=i;
for(int j=1;j<=cnt&&pr[j]*i<maxn;j++){
p[i*pr[j]]=pr[j];
if(p[i]==pr[j]){
mu[i*pr[j]]=mu[i]*pr[j];
break;
}
else mu[i*pr[j]]=mu[i]*(pr[j]-1);
}
}
for(int i=1;i<maxn;i++)
sum[i]=sum[i-1]+mu[i];
}
signed main(){
solve();
int T;cin>>T;
while(T--){
cin>>n>>m;
if(n>m)swap(n,m);
ll ans=0;
for(int l=1;l<=n;l++){
int r=min(n/(n/l),m/(m/l));
ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
l=r;
}
cout<<ans<<endl;
}
return 0;
}