发布时间：2024-08-12

莫比乌斯反演

莫比乌斯函数

• $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$

莫比乌斯反演

若 $F(n)= \sum_{d|n}f(d)$ ,则 $f(n)= \sum_{d|n} \mu (d) F(\frac{n}{d})$
证明：
$\sum_{d|n} \mu(d)F(\frac{n}{d})=\sum_{d|n} \mu(d) \sum_{i|\frac{n}{d}} f(i)=\sum_{i|n} f(i) \sum_{d|\frac{n}{i}} \mu(d)=f(n)(i=n时才有 \mu(\frac{n}{n})=1,其他为0)$

一般使用式子

若 $F(n)= \sum_{n|d}f(d),则f(n)= \sum_{n|d} \mu (\frac{d}{n})F(d)$ 证明：
$\sum_{n|d} \mu(\frac{d}{n})F(d)= \sum_{n|d} \mu(\frac{d}{n}) \sum_{d|i}f(i)= \sum_{n|i}f(i) \sum_{d'|\frac{i}{n}} \mu (d')=f(n)(i=n时才有1)$

常用卷积关系

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

常见积性函数

1. 单位函数 $e(n)=[n=1]$
2. 幂函数 $Id_k(n)=n^k$
3. 因数个数 $d(n)=\sum_{d|n}1$
4. 欧拉函数 $\phi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$

常见公式

• $\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]$
• $n=\sum_{d|n}\phi(d)$

常见结论

$1~n与n互质的个数为\frac{n\cdot \phi(n)}{2}$

P2522 [HAOI2011] Problem b

题意:
给出a,b,c,d,k,求$\sum_{x=a}^b \sum_{y=c}^d gcd(x,y)=k$
思路：
定义 $F(n)=\sum_{x=1}^a \sum_{y=1}^b [n|gcd(x,y)] ,f(n)=\sum_{x=1}^a \sum_{y=1}^b [gcd(x,y)=n]$
$f(n)=\sum_{n|d} \mu(\frac{d}{n})F(d)= \sum_{n|d} \mu(\frac{d}{n}) \lfloor \frac{a}{d} \rfloor \lfloor \frac{b}{d} \rfloor$
令 $d'=\frac{d}{n},=\sum \mu(d') \lfloor \frac{a}{d'n} \rfloor \lfloor \frac{b}{d'n} \rfloor =\sum \mu(d') \lfloor \frac{a'}{d'} \rfloor \lfloor \frac{b'}{d'} \rfloor$

• 然后求的话就是二维前缀和容斥
• 算的时候用整除分块，枚举每个公共的块，使得 $\lfloor \frac{a}{d} \rfloor=\lfloor \frac{b}{d} \rfloor$
• 复杂度为 $O(\sqrt n)$

P1829 [国家集训队] Crash的数字表格 / JZPTAB

题意：

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

思路：

$\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_{i=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)$

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";
}