莫比乌斯反演+例题

参考1

参考2

参考3

问题引入：

入门题

给定N和M和D，求满足1<=x<=N,1<=y<=M且gcd(x,y)=D的点对(x,y)的个数

1<=N,M<=1000000

莫比乌斯函数

μ

μ(n) = 1 , n=1

μ(n) = (-1)k, n=p1 * p2 * … * Pk

（x有奇数个质因子时为-1，x有偶数个质因子时为1）

μ(n) = 0 其他情况（x存在平方因子）

莫比乌斯线性筛：

int prime[MAXN],prime_tot;
bool prime_tag[MAXN];
int mu[MAXN];
void pre_calc(int lim)
{
	mu[1]=1;
	for(int i=2;i<=lim;i++)
	{
		if(!prime_tag[i])
		{
			prime[++prime_tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=prime_tot;j++)
		{
			if(i*prime[j]>lim)break;
			prime_tag[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]==0;
				break;
			}
			else 
			{
				mu[i*prime[j]]=-mu[i];
			}
		}
	}
 } 
           

狄利克雷卷积介绍

狄利克雷卷积：( f * g )(n) = ∑d|nf(d)g(n/d)

d是n的因子

积性函数是指一个定义域为正整体n的算术函数f(n)

积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的函数

完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的函数

若n = p1a1 *p2a2 * … * pkak

则 f(n) = f(p1a1) *f(p2a2) * … * f(pkak)

常见的积性函数：

欧拉函数： φ(n)

n=∑i/nφ(i)

莫比乌斯函数：μ(n)

单位函数：Id(n)=n

不变函数：1(n)=1

幂函数：Idk(n)=nk

因子个数函数：d(n),d= 1 * 1

因子和函数：σ(n),σ=1 * Id

因子函数：σk(n)

狄利克雷卷积单位元：ε = [n==1]

（当n=1时，ε=1，否则等于0）

μ * 1 = ε

莫比乌斯反演

解决问题：

[a’/d]（向下取整）在一段区间内并不变化，所以最多取到2√a’

按照取值将O（√n）段，对μ（d）计算前缀和，然后计算即可

参考练习

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int N=1e5+5;
int p[N+10],check[N+10],tot;
int mu[N],sum[N];
int T,n,m,d,ans;
 
void init(){
	memset(check,1,sizeof check);
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if (check[i]){
			p[++tot]=i;
			mu[i]=-1;
		}
		for (int j=1;j<=tot && p[j]*i<=N;j++){
			check[i*p[j]]=0;
			if (i%p[j]==0){
				mu[i*p[j]]=0;
				break;	
			}
			else mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)sum[i]=mu[i]+sum[i-1];	//维护前缀和
}
 
int calc(int n,int m){	//求[1,n][1,m]区间内互质的(x,y)的对数
	int ret=0;
	if (n>m) swap(n,m);
	for (int L=1,R=0;L<=n;L=R+1){
		R=min(n/(n/L),m/(m/L));		// 分段
		ret+=(sum[R]-sum[L-1])*(n/L)*(m/L);
	}
	return ret;
}
 
int main(){
	init();
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&n,&m,&d);
		ans=calc(n/d,m/d);
		printf("%d\n",ans);
	}
	return 0;
}