莫比乌斯反演-小总结

这两天做了一些莫比乌斯反演的题，现在来稍微总结一下

双亲数

大意：
求

思路：

将d移到判断式的外面去，

原式=

加上莫比乌斯函数的性质

原式可以继续化为

改为枚举d，可以继续化成

注意到这里后面两坨东西我们是可以用分块来处理的，因为u(k)我们可以去处理出来，那么只要找到每一段相同区间里的u(k)函数的一段前缀和即可

关于莫比乌斯函数的预处理，可以通过欧拉筛来实现，这里贴个板子

void moblus()  
{  
    memset(vis,0,sizeof vis);
    mu[1]=1; 
    for(int i=2;i<=N;i++)  
    {  
	    if(!vis[i])
	    {
	    	p[++cnt]=i;
	    	mu[i]=-1;
		} 
        for(int j=1;j<=cnt&&i*p[j]<=N;++j)
        {  
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
            	mu[i*p[j]]=0;
				break; 
			} 
            else mu[i*p[j]]=-mu[i]; 
        }  
    }  
}

其它的就没什么好说的了

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll N=1e6+10;
ll a,b,d;
ll ans=1;
//线性筛法求莫比乌斯函数  
bool vis[N];  //标记 
int p[N];  //质数 
int mu[N];//打表结果 
ll cnt=0;
void moblus()  
{  
    memset(vis,0,sizeof vis);
    mu[1]=1; 
    for(int i=2;i<=N;i++)  
    {  
	    if(!vis[i])
	    {
	    	p[++cnt]=i;
	    	mu[i]=-1;
		} 
        for(int j=1;j<=cnt&&i*p[j]<=N;++j)
        {  
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
            	mu[i*p[j]]=0;//合数
				break; 
			} 
            else mu[i*p[j]]=-mu[i]; 
        }  
    }  
}
ll f(ll n,ll m)
{
	n/=d;m/=d;
	ll ans=0;
	for(ll l=1,r=1;l<=min(n,m);l=r+1) 
	{
		r=min(n/(n/l),m/(m/l));
		ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
	}
	return ans;
}

int main()
{
	cin>>a>>b>>d;
	//ans=a/d*(b/d);
	moblus();
	ll n=min(a,b);
	for(int i=1;i<=n;++i) mu[i]+=mu[i-1];
	ans=f(a,b);
	cout<<ans<<endl;
	return 0;
}  

再来一道狠一点的

P1390 公约数的和

大意：

 思路：

如果要转到可以进行莫比乌斯反演的形式，我们可以先枚举i和j的公因子d

原式=

然后就可以转化为
 

=

那么如果我们令D=d*k的话，

原式可以继续改写为

中间那一坨很明显是可以转化成为欧拉函数的，

最后原式就等于

啊哈，这跟上一道题推出来的式子不是换汤不换药嘛，无非就是求莫比乌斯函数变成了求欧拉函数，基本代码完全没有上面区别

对了，因为这题求的是两两之间的数的公约数的和，不包括数字与数字本身，也不会重复计算，我们最后把这些多余的部分减掉就好了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+10;
ll n;
ll p[N];
ll phi[N];
bool vis[N];
ll cnt=0;
inline void init()
{
	phi[1]=1;
	for(register ll i=2;i<=n;++i)
	{
		if(!vis[i]) p[++cnt]=i,phi[i]=i-1;
		for(register ll j=1;(j<=cnt)&&(i*p[j]<=n);++j)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				phi[i*p[j]]=phi[i]*p[j];
				break;
			}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
	}
	for(ll i=1;i<=n;++i) phi[i]+=phi[i-1];
//	for(int i=1;i<=n;++i) cout<<phi[i]<<' ';
}
inline void solve()
{
	ll ans=0;
	for(register ll l=1,r=1;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans+=(phi[r]-phi[l-1])*(n/l)*(n/l);
	}
	printf("%lld",(ans-n*(n+1)/2)/2);
	//cout<<(ans-n*(n+1)/2)/2<<endl;
}
int main()
{
	scanf("%lld",&n);
	init();
	solve();
	return 0;
}