发布时间：2025-05-22

莫比乌斯反演

莫比乌斯函数

• $n=p_1^{\alpha _1}p_2^{ \alpha _2}...p_k^{ \alpha _k}$
• $Mobius(i)=0, 任意的 \alpha>1$
• $Mobius(i)=1,\alpha=1且k为偶数$
• $Mobius(i)=-1, \alpha =1且k为奇数$
• $S(n)= \sum_{d|n} \mu (d),当n=1时,S(n)=1;当n>1,S(n)=0$

推导常用公式

1. 若 $F(n)= \sum_{d|n}f(d)$ ,则 $f(n)= \sum_{d|n} \mu (d) F(\frac{n}{d})$ ，这是莫比乌斯反演的正确公式，但是用这种方法很多时候特别难推，因此基本不会用到

2. $\sum_{d|n} \mu(d)= [n=1]$

3. $\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]= \sum_{i=1}^{\frac{n}{d} }\sum_{j=1}^{\frac{m}{d}} [\gcd(i,j)=1]$，2和3公式通常会一起使用

4. $\sum_{d|n} \phi(d)=n$

5. $\sum_{d|n} \mu(d)\frac{n}{d}=\phi(d)$

为了好写，推导默认下取整

求$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k]$

$$\sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=k]= \sum_{i=1}^{\frac{n}{k} }\sum_{j=1}^{\frac{m}{k}} [gcd(i,j)=1]=\\ \sum_{i=1}^{\frac{n}{k}} \sum_{j=1}^{\frac{m}{k}}\sum_{d|\gcd(i,j)}\mu(d)= \sum_{d=1}\mu(d)\sum_{i=1}^{\frac{n}{k}}[d|i]\sum_{j=1}^{\frac{m}{k}}[d|j]=\\ \sum_d^{min(\frac{n}{k},\frac{m}{k})} \mu(d)\frac{n}{kd}\frac{m}{kd}$$

int f(int a,int b,int k){
    int res=0;
    a=a/k,b=b/k;
    int n=min(a,b);
    for(int l=1,r;l<=n;l=r+1){
        r=min({n,a/(a/l),b/(b/l)});
        res+=(sum[r]-sum[l-1])*(a/l)*(b/l);//sum为mu前缀和
    }
    return res;
}

求$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)$

$\sum_{k=1}^{\min(n,m)}\sum_d^{min(\frac{n}{k},\frac{m}{k})} \mu(d)\frac{n}{kd}\frac{m}{kd}$

令$T=kd$,$\sum_{T=1}^n \sum_{k|T}\mu(\frac{T}{k})\frac{n}{T}\frac{m}{T}$

$\sum_{k|T}\mu(\frac{T}{k})$可以调和级数预处理

int mu[N],sum[N];
bool st[N];
vector<int> prime;
void sieve(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            st[i]=1;
            mu[i]=-1;
            prime.push_back(i);
        }
        for(auto p:prime){
            if(p*i>n)break;
            st[p*i]=1;
            if(i%p==0)break;
            mu[p*i]=-mu[i];
        }
    }
    for(auto p:prime){
        for(int i=p;i<=n;i+=p)sum[i]+=mu[i/p];
    }
    for(int i=1;i<=n;i++){
        sum[i]+=sum[i-1];
    }
}
int f(int a,int b){
    int res=0;
    int n=min(a,b);
    for(int l=1,r;l<=n;l=r+1){
        r=min({n,a/(a/l),b/(b/l)});
        res+=(sum[r]-sum[l-1])*(a/l)*(b/l);
    }
    return res;
}
void solve(){
    int a,b,k;
    cin>>a>>b;
    cout<<f(a,b)<<"\n";
}

求$\sum_{i=1}^n \sum_{j=1}^m lcm(i,j)$

$\sum_{i=1}^n \sum_{j=1}^m lcm(i,j)=\sum_{i=1}^n \sum_{j=1}^m \frac{ij}{gcd(i,j)}$

$=\sum_{i=1}^n \sum_{j=1}^m \sum_{d=1}^n ij\frac{[gcd(i,j)=d]}{d}=\sum_{d=1}^n \sum_{id=1}^{n} \sum_{jd=1}^{m} ijd^2\frac{[gcd(id,jd)=d]}{d}$

$=\sum_{d=1}^n \sum_{i=1}^{\frac{n}{d}} \sum_{j=1}^{\frac{m}{d}}ijd[gcd(i,j)=1]=\sum_{d=1}^n \sum_{i=1}^{\frac{n}{d}} \sum_{j=1}^{\frac{m}{d}}ijd \sum_{k|gcd(i,j)} \mu(k)$

$=\sum_{d=1}^n \sum_{i=1}^{\frac{n}{d}} \sum_{j=1}^{\frac{m}{d}}ijd \sum_{k=1}^{\frac{n}{d}} \mu(k)[k|i][k|j]$

$=\sum_{d=1}^nd \sum_{k=1}^{\frac{n}{d}} \mu(d) \sum_{ik=1}^{\frac{n}{d}}ik \sum_{jk=1}^{\frac{m}{d}}jk$

$=\sum_{d=1}^nd \sum_{k=1}^{\frac{n}{d}} \mu(k)k^2 \sum_{i=1}^{\frac{n}{kd}}i \sum_{j=1}^{\frac{m}{kd}}j$

定义 $F(n,m)= \sum_{k=1}^n \mu(k)k^2 \sum_{i=1}^{\frac{n}{k}}i\sum_{j=1}^{\frac{m}{k}}j$

$G(n,m)=\sum_{i=1}^n \sum_{j=1}^m ij=\frac{n*(n+1)}{2}*\frac{m*(m+1)}{2}$

分块套分块解决，复杂度为 $O(n)$

//P1829
int n,m;
int mu[N],sum[N];
bool vis[N];
vector<int> prime;
void sieve(){
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			vis[i]=1;
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0;j<prime.size()&&prime[j]*i<N;j++){
			vis[prime[j]*i]=1;
			if(i%prime[j]==0)break;
			mu[prime[j]*i]=-mu[i];
		}
	}
	for(int i=1;i<N;i++)sum[i]=(sum[i-1]+mu[i]*i%mod*i%mod)%mod,sum[i]=(sum[i]+mod)%mod;
}
int G(int n,int m){
	return n*(n+1)/2%mod*(m*(m+1)/2%mod)%mod;
}
int F(int n,int m){
	int res=0;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res=(res+((sum[r]-sum[l-1])%mod+mod)%mod*G(n/l,m/l)%mod)%mod;
	}
	return res;
}
int cal(int n,int m){
	if(n>m)swap(n,m);
	int res=0;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res=(res+(r-l+1)*(l+r)/2%mod*F(n/l,m/l)%mod)%mod;
	}
	return res;
}
void solve(){
	int n,m;
	cin>>n>>m;
	sieve();
	cout<<cal(n,m)<<"\n";
}

P3704 [SDOI2017] 数字表格

题意：

求 $\prod_{i=1}^n\prod_{j=1}^m f(\gcd(i,j)) ,f为斐波那契$

思路：

$\prod_{i=1}^n\prod_{j=1}^m\prod_{d=1}^nf(d)[\gcd(i,j)=d]$

$\prod_{d=1}^nf(d)^{\prod_{i=1}^n\prod_{j=1}^m[\gcd(i,j)=d]}=\prod_{d=1}^nf(d)^{\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]}$

$\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]=\sum_{k=1}^{\frac{n}{d}} \mu(k)\sum_{i=1}^{\frac{n}{d}}[k|i]\sum_{i=1}^{\frac{m}{d}}[k|j]$

$=\sum_{k=1}^{\frac{n}{d}} \mu(k)\lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor$

$令T=dk,k=\frac{T}{d},=\sum_{T=1}^n \mu(\frac{T}{d})\frac{n}{T}\frac{m}{T}$

$原式=\prod_{T=1}^n(\prod_{d=1}^nf(d)^{\mu(\frac{T}{d})})^{\frac{n}{T}\frac{m}{T}}$

$令F(j)=\prod_{i=1}^nf(i)^{\mu(\frac{j}{i})},需要预处理f(j)，然后每个测试样例O(\sqrt n)算$

bool vis[N];
int mu[N],F[N],f[N],invf[N];
vector<int> prime;
int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
void init(){
	mu[1]=1;
	f[1]=F[0]=F[1]=invf[0]=invf[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			prime.push_back(i);
			mu[i]=-1;
		}
		for(int j=0;j<prime.size()&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
			mu[i*prime[j]]=-mu[i];
		}
		f[i]=(f[i-1]+f[i-2])%mod;
		invf[i]=qpow(f[i],mod-2);
		F[i]=1;	
	}
	for(int i=1;i<N;i++){
		for(int j=i;j<N;j+=i){
			if(mu[j/i])F[j]=(F[j]*(mu[j/i]==1?f[i]:invf[i]))%mod;
		}
	}
	for(int i=2;i<N;i++)F[i]=F[i]*F[i-1]%mod;
}
int cal(int n,int m){
	if(n>m)swap(n,m);
	int ans=1;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		int s=F[r]*qpow(F[l-1],mod-2)%mod; 
		ans=ans*qpow(s,(n/l)*(m/l))%mod;
	}
	return ans;
}
void solve(){
	int n,m;
	cin>>n>>m;
	cout<<cal(n,m)<<"\n";
}

P3327 [SDOI2015] 约数个数和

题意：

$d(x)是x的约数个数，\sum_{i=1}^n \sum_{j=1}^md(ij)$

思路：

$d(ij)=\sum_{x|i}\sum_{y|i}[\gcd(x,y)=1]=\sum_{x|i}\sum_{y|i}\sum_{p|\gcd(x,y)} \mu(p)$

$=\sum_{p=1}^{min(i,j)}\sum_{x|i}\sum_{y|i}[p|\gcd(x,y)]\mu(p)$

$=\sum_{p|i,p|j}\mu(p)\sum_{x|i}\sum_{y|j}[p|\gcd(x,y)]=\sum_{p|i,p|j}\mu(p)\sum_{x|\frac{i}{p}}\sum_{y|\frac{j}{p}}1=\sum_{p|i,p|j}\mu(p)d(\frac{i}{p})d(\frac{j}{p})$

带入原式得，$\sum_{i=1}^n\sum_{j=1}^m\sum_{p|i,p|j}\mu(p)d(\frac{i}{p})d(\frac{j}{p})=\sum_{p=1}^{min(n,m)}\sum_{i=1}^{\frac{n}{p}}\sum_{j=1}^{\frac{m}{p}}\mu(p)d(i)d(j)$

bool vis[N];
int mu[N],d[N],t[N];//t为最小质因子出现次数
vector<int> prime;
void init(){
	mu[1]=d[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]){
			vis[i]=1;
			prime.push_back(i);
			mu[i]=-1;
			d[i]=2;
			t[i]=1;
		}
		for(int j=0;j<prime.size()&&i*prime[j]<N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				d[i*prime[j]]=d[i]/(t[i]+1)*(t[i]+2);
				t[i*prime[j]]=t[i]+1;
				break;
			}
			mu[i*prime[j]]=-mu[i];
			d[i*prime[j]]=d[i]*2;
			t[i*prime[j]]=1;
		}
	}
	for(int i=2;i<N;i++){
		d[i]+=d[i-1],mu[i]+=mu[i-1];
	}
}
int cal(int n,int m){
	if(n>m)swap(n,m);
	int ans=0;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		ans+=(mu[r]-mu[l-1])*d[n/l]*d[m/l];
	}
	return ans;
}
void solve(){
	int n,m;
	cin>>n>>m;
	cout<<cal(n,m)<<"\n";
}

求$\sum_{i=1}^n \sum_{j=1}^n ij\gcd(i,j)$

$$\sum_{k=1}^n k^3 \sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{n}{k}} ij[gcd(i,j)=1]=\\ \sum_{k=1}^n k^3 \sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{n}{k}} \sum_{d|\gcd(i,j)}\mu(d)ij=\\ \sum_{k=1}^n k^3 \sum_{d=1}^{\frac{n}{k}}\mu(d)d^2\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{n}{kd}}ij=\\ 令g(x)=(\frac{n(n+1)}{2})^2,T=kd\\ \sum_{T=1}^ng(\frac{n}{T})T^2\sum_{k|T}\mu(\frac{T}{k})k=\sum_{T=1}^ng(\frac{n}{T})T^2\phi(T)$$

如果$n \geq 1e9$,如P3768,函数$f(x)=x^2\phi(x)$用杜教筛求解

vector<int> phi,sum_phi;
vector<int> prime;
vector<bool> st;
int P,inv2,inv6;
int qpow(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
void sieve(int n){
    phi.resize(n+1);
    sum_phi.resize(n+1);
    st.resize(n+1);
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime.push_back(i);
            phi[i]=i-1;
        }
        for(auto p:prime){
            if(p*i>n)break;
            st[p*i]=1;
            if(i%p==0){
                phi[p*i]=phi[i]*p;
                break;
            }
            else{
                phi[p*i]=phi[i]*(p-1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum_phi[i]=(sum_phi[i-1]+phi[i]*i%P*i%P)%P;
    }
}
unordered_map<int,int> mp;
int G(int x){
    x%=P;
    return x*(x+1)%P*(2*x+1)%P*inv6%P;
}
int g(int x){
    x%=P;
    return x*(x+1)%P*inv2%P*x%P*(x+1)%P*inv2%P;
}
int S(int x){
    if(x<sum_phi.size())return sum_phi[x];
    if(mp.count(x))return mp[x];
    int res=g(x);
    int pre=1,cur;
    for(int l=2,r;l<=x;l=r+1){
        r=x/(x/l);
        cur=G(r);
        res-=(cur-pre+P)%P*S(x/l)%P;
        res=(res%P+P)%P;
        pre=cur;
    }
    return mp[x]=(res%P+P)%P;
}
int f(int n){
    int res=0;
    int pre=0,cur;
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l);
        int cur=S(r);
        res=(res+g(n/l)*(cur-pre+P)%P)%P;
        pre=cur;
    }
    return (res%P+P)%P;
}
void solve(){
    int n;
    cin>>P>>n; 
    inv2=qpow(2,P-2,P);
    inv6=qpow(6,P-2,P);
    sieve(pow(n,2.0/3));  
    cout<<f(n)<<"\n";
}

求$\sum_{i=1}^n\sum_{j=i+1}^n lcm(a_i,a_j)$

利用一个桶记录出现个数，$t_i$表示$i$的出现个数

$\sum_{i=1}^n\sum_{j=i+1}^n lcm(a_i,a_j)=\frac{\sum_{i=1}^n\sum_{j=1}^n lcm(a_i,a_j)-\sum_{i=1}^n a_i}{2}$

$\sum_{i=1}^n\sum_{j=1}^n lcm(a_i,a_j)=\sum_{i=1}^{Max}\sum_{j=1}^{Max}lcm(i,j)\cdot t_i \cdot t_j$

反演得到$\sum_{T=1}^{n} T(\sum_{i=1}^{\frac{n}{T}}i \times t_{iT})^2 \sum_{k|T}\mu(k)k$

详见P3911和agc038c

// 求\sum_{i=1}^n\sum_{j=1}^n lcm(a[i],a[j])
int mu[N],sum[N],t[N],sum_t[N];
bool st[N];
vector<int> prime;
void sieve(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime.push_back(i);
            mu[i]=-1;
        }
        for(auto x:prime){
            if(x*i>n)break;
            st[x*i]=1;
            if(i%x==0){
                mu[x*i]=0;
                break;
            }
            else mu[x*i]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=i){
            sum[j]+=mu[i]*i;
        }
    }
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        t[x]++;
    }
    sieve(1e6);
    int ans=0;
    for(int T=1;T<=1e6;T++){
        int res=0;
        for(int i=1;i<=1e6/T;i++)res+=i*t[i*T];
        ans+=T*res*res*sum[T];
    }
    cout<<ans<<"\n";
}