首页 > 其他分享 >「学习笔记」莫比乌斯反演

「学习笔记」莫比乌斯反演

时间:2023-09-15 10:12:29浏览次数:39  
标签:lfloor right frac limits 乌斯 sum rfloor 反演 莫比

开新坑了。QWQ

前置芝士:数论分块。(之后再说。QWQ)

积性函数

定义

一个数论函数 \(f(n)\) 满足 \(f(xy)=f(x) \times f(y)\)(\(\gcd(x,y)=1\)),则称 \(f(n)\) 是积性函数。

莫比乌斯函数:

\(\mu(n) = \begin{cases}1 &n=1\\0 &n\ \text{含有平方因子}\\(-1)^k &k\text{为}\ n\ \text{的本质不同质因子个数} \end{cases}\)


P3455 [POI2007] ZAP-Queries

下面两道题的手推的式子

求:

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k] \]

经典把 \(\gcd(i,j)=k\) 转化为 \(\gcd(i,j)=1\)。

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(\frac{i}{k},\frac{j}{k})=1][i|k][j|k] \]

\[\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1] \]

\[\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d) \]

\[\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|i,d|j}\mu(d) \]

\[\sum\limits_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d=1}^{\min(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor)}\mu(d)[d|i][d|j] \]

\[\sum\limits_{d=1}^{\min(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j] \]

\[\sum\limits_{d=1}^{\min(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor)}\mu(d)\left\lfloor\frac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor\left\lfloor{\frac{\left\lfloor\frac{m}{k}\right\rfloor}{d}}\right\rfloor \]

线性筛一遍莫比乌斯函数再用数论分块即可。

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 50010
using namespace std;
int t,n,m,a,b,k,ans;
int mu[MAXN],num[MAXN];
bool vis[MAXN];
vector<int> prm;
void sieve(){
	mu[1]=1;num[1]=1;
	for(int i=2;i<=5e4;i++){
		if(!vis[i]){
			prm.push_back(i);
			mu[i]=-1;
		}
		num[i]=num[i-1]+mu[i];
		for(int j=0;j<prm.size() and i*prm[j]<=5e4;j++){
			vis[i*prm[j]]=true;
			if(i%prm[j]==0) break;
			mu[i*prm[j]]=-mu[i];
		}
	}
}
void calc(){
	int r;
	for(int l=1;l<=a;l=r+1){
		r=min(a/(a/l),b/(b/l));
		ans+=(num[r]-num[l-1])*(a/l)*(b/l);
	}
}
int main(){
	cin>>t;
	sieve();
	while(t--){
		ans=0;
		cin>>n>>m>>k;
		a=n/k;b=m/k;
		if(a>b) swap(a,b);
		calc();
		cout<<ans<<"\n";
	}
	return 0;
}

P2522 [HAOI2011] Problem b

就是用容斥原理搞一下,之后就和上面的一样了。

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 50010
using namespace std;
int t,n,m,a,b,c,d,k;
int mu[MAXN],num[MAXN];
bool vis[MAXN];
vector<int> prm;
void sieve(){
	mu[1]=1;num[1]=1;
	for(int i=2;i<=5e4;i++){
		if(!vis[i]){
			prm.push_back(i);
			mu[i]=-1;
		}
		num[i]=num[i-1]+mu[i];
		for(int j=0;j<prm.size() and i*prm[j]<=5e4;j++){
			vis[i*prm[j]]=true;
			if(i%prm[j]==0) break;
			mu[i*prm[j]]=-mu[i];
		}
	}
}
int calc(int x,int y){
	n=x/k;m=y/k;
	if(n>m) swap(n,m);
	int r,ans=0;
	for(int l=1;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		ans+=(num[r]-num[l-1])*(n/l)*(m/l);
	}
	return ans;
}
int main(){
	sieve();
	cin>>t;
	while(t--){
		cin>>a>>b>>c>>d>>k;
		cout<<calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1)<<"\n";
	}
	return 0;
}

P2257 YY的GCD PGCD - Primes in GCD Table

说句题外话,我是先写的这道题,再写的上面那两道题。QWQ

用图画手推的式子,很抽象,就当图个乐就行了。

下面正式推式子。

求:

\[\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j) \in \operatorname{prime}] \]

经典把 \(\gcd(i,j)=k\) 转化为 \(\gcd(i,j)=1\)。

\[\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{p \in \operatorname{prime},p|i,p|j}[\gcd(\frac{i}{p},\frac{j}{p})=1] \]

\[\sum\limits_{i=1}^n \sum\limits_{j=1}^m \sum\limits_{p \in \operatorname{prime}}[\gcd(\frac{i}{p},\frac{j}{p})=1][p|i][p|j] \]

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} [\gcd(i,j)=1] \]

然后用莫比乌斯反演。

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} \sum\limits_{d|\gcd(i,j)}\mu(d) \]

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} \sum\limits_{d|i,d|j}\mu(d) \]

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} \sum\limits_{d=1}^{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}\mu(d)[d|i][d|j] \]

这里就把 \(n\) 当做 \(\min(n,m)\)。

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} \sum\limits_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(d)[d|i][d|j] \]

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor} [d|i]\sum\limits_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor} [d|j] \]

\[\sum\limits_{p \in \operatorname{prime}}\sum\limits_{d=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\mu(d)\left\lfloor\frac{n}{pd}\right\rfloor\left\lfloor\frac{m}{pd}\right\rfloor \]

我们设 \(T=pd\),并将式子转换成枚举 \(T\)。

\[\sum\limits_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum\limits_{p \in \operatorname{prime},p|T}\mu(\frac{T}{p}) \]

可以发现右面的式子可以提前求出。左面的式子数论分块即可。

#include<bits/stdc++.h>
#define XD 114514
#define MAXN 10000010
using namespace std;
int t,n,m;
int mu[MAXN],f[MAXN],sum[MAXN];
bool vis[MAXN];
vector<int> prm;
void sieve(){
	mu[1]=1;
	for(int i=2;i<=1e7;i++){
		if(!vis[i]){
			prm.push_back(i);
			mu[i]=-1;
		} 
		for(int j=0;j<prm.size();j++){
			if(i*prm[j]>1e7) break;
			vis[i*prm[j]]=true;
			if(i%prm[j]==0) break;
			mu[i*prm[j]]=-mu[i];
		}
	}
	for(int i=0;i<prm.size();i++){
		for(int j=1;j<=1e7;j++){
			if(prm[i]*j>1e7) break;
			f[prm[i]*j]+=mu[j];
		}
	}
	for(int i=1;i<=1e7;i++) sum[i]=sum[i-1]+f[i];
}
long long ans;
void solve(){
	int r=0;if(n>m) swap(n,m);
	for(int l=1;l<=n;l=r+1){
		int nem1=n/l,nem2=m/l;
		r=min(n/nem1,m/nem2);
		ans+=1ll*(sum[r]-sum[l-1])*(n/l)*(m/l);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;
	sieve();
	while(t--){
		ans=0;
		cin>>n>>m;
		solve();
		cout<<ans<<"\n";
	}
	return 0;
}

学习建议

建议看以下的博客,讲的非常好,反正我的也看不懂。QWQ

浅谈莫反

狄利克雷卷积和莫比乌斯反演

(我本人最推荐这两个。QWQ)

莫比乌斯反演-让我们从基础开始(洛谷日报上的)

莫比乌斯反演

peng-ym 的杜教筛

算法学习笔记(35): 狄利克雷卷积

标签:lfloor,right,frac,limits,乌斯,sum,rfloor,反演,莫比
From: https://www.cnblogs.com/wdgm4/p/17704213.html

相关文章

  • 可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫
    P8946TheLostSymbol这种类型的dp的特点就是大部分转移形如\(f(i,j)\rightarrowf(i+1,j+1)\)之类的,并且当以上转移出现时原数组被清空,这就可以用一个deque来维护,然后对于全局赋值/全局加,需要对每个位置维护一个时间戳,并记录上一次赋值/加是什么时候,以便标记下传。(貌似......
  • 『学习笔记』莫比乌斯反演
    对前置知识的再补充欧拉函数:其中一个性质:\[n=\sum_{d\midn}\varphi(d).\]用狄利克雷卷积表示:\[\operatorname{id}=\varphi*1.\]莫比乌斯函数:其中一个性质(或叫做定义式):\[\sum_{d\midn}\mu(d)=[n=1].\]用狄利克雷卷积表示:\[\varepsilon=\mu*1.\]......
  • ENVI+ERDAS实现Hyperion叶绿素含量反演:经验比值法、一阶微分法
    本文介绍基于ENVI与ERDAS软件,依据Hyperion高光谱遥感影像,采用经验比值法、一阶微分法等,对叶绿素含量等地表参数加以反演的具体操作。目录1前期准备与本文理论部分1.1几句闲谈1.2背景知识1.2.1Hyperion数据介绍1.2.2遥感图像分类方法1.2.3大气校正1.2.4反演算法2基于经验......
  • 反演小记
    反演反演,可以理解为两个事物通过某种关系的互相转化。基本推论设\(F,G\),满足\(F(n)=\sumV[n,i]G(i)\),其中\(V\)为矩阵,将\(F,G\)看成列向量,可以写做\(F=V*G\),那么我们可以容易推出\(G=V^{-1}*F\),这就是反演的过程,而一些特殊的反演即是利用了\(V\)和\(V^{-1}......
  • 【算法学习笔记】max-min容斥 极值反演
    max-min容斥(极值反演)即为下式;\[\begin{equation}\max\{S\}=\sum_{T\subseteqS}(-1)^{|T|+1}\min\{T\}\label{aa}\end{equation}\]\[\begin{equation}\min\{S\}=\sum_{T\subseteqS}(-1)^{|T|+1}\max\{T\}\label{ab}\end{equation}\]证明:证明\(\ref......
  • 「学习笔记」莫比乌斯反演
    「学习笔记」莫比乌斯反演点击查看目录目录「学习笔记」莫比乌斯反演前置知识整除分块积性函数线性筛任意积性函数莫比乌斯反演莫比乌斯函数莫比乌斯反演公式例题[HAOI2011]ProblembYY的GCD[SDOI2014]数表DZYLovesMath[SDOI2015]约数个数和[SDOI2017]数字表格于神之......
  • 『学习笔记』欧拉函数、莫比乌斯函数、高位前缀和、狄利克雷前后缀和
    欧拉函数定义又叫做\(\varphi\)函数,\(\varphi(x)\)用来描述不大于\(x\)且与\(x\)互素的数的个数。性质满足一切积性函数的性质。若\(a\botb\),则\(f(a\timesb)=f(a)\timesf(b)\).能用线性筛或埃氏筛求出。\(\text{from}\1\\text{to}\n\)中与......
  • 学习笔记_莫比乌斯反演
    前置知识:整除分块莫比乌斯函数(\(\mu\))$\mu(d)=\begin{cases}1&(d=1)\\(-1)^{k}&\forallC_i=1\\0&\existsC_i>1\end{cases}$性质1.对于任意正整数\(n\),$$\sum_{d|n}\mu(d)=[n=1]$$[]是一个返回bool型值的判断,当[]内条件成立时返回1,否则返回0.2.对于任意......
  • 单位根反演
    一个非常不阳间的关于单位根的性质:\[\forallk,[n∣k]=\frac{1}{n}\sum_{i=0}^{n−1}\omega^{ik}_{n}\]证明:若\(n∣k\),则有\[Ans=\frac{1}{n}\sum_{i=0}^{n−1}ω^{ink^′}_n=\frac{1}{n}\sum_{i=0}^{n−1}1=1\]否则,等比数列求和有\[Ans=\frac1n\frac{ω^0_n−ω^{nk}_n}......
  • 莫比乌斯反演
    机房卷哥让我写的。大部分是习题总结。不如Wiki两个积性函数\(f,g\),它们的狄利克雷卷积(Dirichlet卷积)为\[h(n)=(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]记为\(h=f*g\).狄利克雷卷积满足交换律,结合律,且得到的函数也是积性函数。定义\[\epsilon(n)=\lb......