专栏文章

速通莫反

wwallace_QwQ
算法·理论参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip3tkd1
此快照首次捕获于
2025/12/03 05:42
3 个月前
此快照最后确认于
2025/12/03 05:42
3 个月前
查看原文

一.积性函数

TIP. 其实这部分并不是太重要，只需要记得这些函数的定义和怎么用线性筛 O(n)O(n) 求解即可。

(1).定义

积性函数：对于函数 f(x)f(x)，若 ∀a,b∈N+,gcd⁡(a,b)=1,f(ab)=f(a)f(b)\forall a,b\in\mathbb{N}^+,\gcd(a,b)=1,f(ab)=f(a)f(b)，则称 f(x)f(x) 为积性函数。
完全积性函数：对于函数 f(x)f(x)，若 ∀a,b∈N+,f(ab)=f(a)f(b)\forall a,b\in\mathbb{N}^+,f(ab)=f(a)f(b)，则称 f(x)f(x) 为完全积性函数。
  • 常见的积性函数：φ,μ,σ,d\varphi,\mu,\sigma,d
  • 常见的完全积性函数：ε,I,id\varepsilon,I,id
其中：ε(n)=[n=1],I(n)=1,id(n)=n\varepsilon(n)=\left[n=1\right],I(n)=1,id(n)=n
积性函数的性质：
  • 设 n=∏piαin=\prod p_i^{\alpha_i}，那么 f(n)=∏f(piαi)f(n)=\prod f(p_i^{\alpha_i})
    • 于是可以用线性筛求出 g(n)=p1α1g(n)=p_1^{\alpha_1}，然后 f(n)=f(g(n))f(ng(n))f(n)=f(g(n))f(\frac{n}{g(n)})，在 O(n)O(n) 时间内预处理积性函数的值。
  • 若 f(n)f(n)，g(n)g(n) 都是积性函数，那么 fgfg，fg\frac{f}{g} 都是积性函数。

(2).欧拉函数 φ\varphi

1.定义

若 n=∏i=1spikin=\prod_{i=1}^{s}{p_i}^{k_i}，其中 pip_i 为质数，则 φ(n)=n∏i=1spi−1pi\varphi(n)=n\prod_{i=1}^{s}\frac{p_i-1}{p_i}，表示小于等于 nn 和 nn 互质的数的个数$

2.性质：

  1. 若n为质数，φ(n)=n−1若n为质数，\varphi(n)=n-1
  2. 若n为奇数，φ(n)=φ(2n)若n为奇数，\varphi(n)=\varphi(2n)
  3. 若a⊥b,φ(ab)=φ(a)φ(b)若a \perp b,\varphi(ab)=\varphi(a)\varphi(b)
  4. n=∑d∣nφ(d)n=\sum_{d \mid n}\varphi(d)
  5. 若n=pk,且p为质数，φ(n)=pk−pk−1若n=p^k,且p为质数，\varphi(n)=p^k-p^{k-1}

3.求法

a.单个：

CPP
int euler_phi(int n){
	int ans=n,sq=sqrt(n);
	for1(i,2,sq)
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0) n/=i;
		}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}

b.多个：

筛法：筛法：
设p1为n的最小质因子，n′=np1，显然有φ(p1)=p1−1设p_1为n的最小质因子，n'=\frac{n}{p_1}，显然有\varphi(p_1)=p_1-1
若n′ mod p1=0,φ(n)=p1∗φ(n′)若n'\bmod p_1=0,\varphi(n)=p_1*\varphi(n')
若n′ mod p1≠0,φ(n)=φ(p1)∗φ(n′)若n'\bmod p_1\ne0,\varphi(n)=\varphi(p_1)*\varphi(n')
CPP
void euler_phi(int n){
	phi[1]=1;
	for1(i,2,n){
		if(!vis[i]) pri.p_b(i),phi[i]=i-1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				phi[i*j]=phi[i]*j;
				break;
			}
			phi[i*j]=phi[i]*phi[j];
		}
	}
}

(3).莫比乌斯函数 μ\mu

1.定义

μ(n)={1n=10n的质因子最高次数>1(−1)kn的质因子最高次数=1\mu(n)= \begin{cases} 1&n=1\\ 0&n的质因子最高次数>1\\ (-1)^k&n的质因子最高次数=1 \end{cases}
其中 kk 为 nn 的质因子个数。

2.性质

{1n=10n≠1\begin{cases} 1&n=1\\ 0&n\ne1 \end{cases}
即 ∑d∣nμ(d)=ε(n),μ∗1=ε\sum\limits_{d\mid n}\mu(d)=\varepsilon(n),\mu\ast1=\varepsilon

3.求法

线性筛：
CPP
void get_mu(int n){
	mu[1]=1;
	for1(i,2,n){
		if(!vis[i]) pri.p_b(i),mu[i]=-1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				mu[i*j]=0;
				break;
			}
			mu[i*j]=-mu[i];
		}
	}
}

(4).约数之和 σ\sigma 与 约数个数 dd

1.定义

若 n=p1α1×p2α2×…pnαnn=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\dots p_n^{\alpha_n}
则：
d(n)=(1+α1)×(1+α2)×⋯×(1+αn)d(n)=(1+\alpha_1)\times(1+\alpha_2)\times\dots\times(1+\alpha_n)
σ(n)=(1+p11+p12+⋯+p1α1)×(1+p21+p22+⋯+p2α1)×⋯×(1+pn1+pn2+⋯+pnα1)\sigma(n)=(1+p_1^1+p_1^2+\dots+p_1^{\alpha_1})\times(1+p_2^1+p_2^2+\dots+p_2^{\alpha_1})\times\dots\times(1+p_n^1+p_n^2+\dots+p_n^{\alpha_1}) =∏i=1n(∑j=0αipij)=\prod\limits_{i=1}^n(\sum_{j=0}^{\alpha_i}p_i^j) =∏i=1n1−piαi+11−pi=\prod\limits_{i=1}^n\frac{1-p_i^{\alpha_i+1}}{1-p_i}

2.求法

  1. 线性筛求 dd
tit_i 表示 ii 的最小质因子的次数，即 min⁡(α1,…,αn)\min(\alpha_1,\dots,\alpha_n)。
CPP
void make_d(){
    t[1]=d[1]=1;
    for1(i,2,n){
		if(!vis[i]) pri.p_b(i),t[i]=1,d[i]=2;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				t[i*j]=t[i]+1;
				d[i*j]=d[i]*(t[i*j]+1)/(t[i]+1);
				break;
			}
			t[i*j]=1;
			d[i*j]=d[i]*d[j];
		}
    }
}
  1. 线性筛求 σ\sigma
ti=min⁡(∑j=0α1p1j,…,∑j=0αnpnj)t_i=\min(\sum_{j=0}^{\alpha_1}p_1^j,\dots,\sum_{j=0}^{\alpha_n}p_n^j)。
CPP
void make_sgm(){
    sigma[1]=1;
    for1(i,2,n){
		if(!vis[i]) pri.p_b(i),t[i]=i+1,sigma[i]=i+1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				t[i*j]=t[i]*j+1;
                sigma[i*j]=sigma[i]*t[i*j]/t[i];
				break;
			}
			t[i*j]=j+1;
			sigma[i*j]=sigma[i]*sigma[j];
		}
    }
}

二.数论分块

oi-wiki
一般用来求形如 ∑i=1nf(i)g(⌊ni⌋)\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor)
若可以 O(1)O(1) 计算 f(r)−f(l)f(r)-f(l) 时。
我们考虑将 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 相同的数分块计算以使复杂度降至 O(n×poly(n))O(\sqrt n\times poly(n))
其中的 poly(n)poly(n) 是计算 g(i)g(i) 一次的复杂度。
最简单的例子： ∑i=1n⌊ni⌋\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor
证：按 ⌊ni⌋\lfloor\frac{n}{i}\rfloor 相同的数分块数是 n\sqrt{n} 量级的。
若 i≤ni\le \sqrt{n} 则 ⌊ni⌋=⌊n1⌋…⌊nn⌋≥n\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{1}\rfloor\dots\lfloor\frac{n}{\sqrt{n}}\rfloor\ge\sqrt{n} 最多有 n\sqrt{n} 个取值。
若 i>ni> \sqrt{n} 则 ⌊ni⌋<n\lfloor\frac{n}{i}\rfloor<\sqrt{n} 最多有 n\sqrt{n} 个取值。
证毕。
所以数论整除可以将 O(n)O(n) 降为 O(n)O(\sqrt{n})
例题：UVA11526 H(n)
CPP
LL H(LL n){
	LL ans=0;
	for(LL i=1,j;i<=n;i=j+1){
		j=n/(n/i);
		ans+=(j-i+1)*(n/i);
	}
	return ans;
}

三.狄利克雷卷积

  • 两个数论函数的狄利克雷卷积：
(f∗g)(n)=∑d∣nf(d)g(nd)=∑a⋅b=nf(a)g(b)\begin{aligned} (f\ast g)(n) &=\sum\limits_{d\mid n}f(d)g(\frac{n}{d})\\ &=\sum\limits_{a\cdot b=n}f(a)g(b) \end{aligned}
  • 满足：
    • 交换律
    • 结合律
    • 分配率
    • 单位元：f∗ε=ff\ast\varepsilon=f
    • f∗gf\ast g 也是积性函数
    • 若 f∗g=εf\ast g=\varepsilon，则称 g(x)g(x) 是 f(x)f(x) 的逆元，若 f(x)f(x) 为积性函数，则 g(x)g(x) 为积性函数
例子：
ϵ=μ∗1  ⟺  ϵ(n)=∑d∣nμ(d)d=1∗1  ⟺  d(n)=∑d∣n1σ=id∗1  ⟺  σ(n)=∑d∣ndφ=μ∗id  ⟺  φ(n)=∑d∣nd⋅μ(nd)\begin{aligned} \epsilon=\mu\ast1&\iff\epsilon(n)=\sum\limits_{d\mid n}\mu(d)\\ d=1\ast1&\iff d(n)=\sum\limits_{d\mid n}1\\ \sigma=id\ast1&\iff\sigma(n)=\sum\limits_{d\mid n}d\\ \varphi=\mu\ast id&\iff\varphi(n)=\sum\limits_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned}
但是这么多函数之间进行狄利克雷卷积，很难记住结果怎么办？
有一种利用生成函数辅助的方法。
令 pp 表示任意质数。
首先我们有 (f∗g)(pk)=∑k1+k2=kf(pk1)g(pk2)(f\ast g)(p^k)=\sum\limits_{k_1+k_2=k}f(p^{k_1})g(p^{k_2})
定义生成函数 f~(x)=∑kf(pk)xk\tilde{f}(x)=\sum_{k}f(p^k)x^k
则 f∗g~=f~⋅g~\tilde{f\ast g}=\tilde{f}\cdot\tilde{g}
首先积性函数只需考虑定义域为 pkp^k 的值，所以以下函数定义域均为 pkp^k
  • μ~(x)=1−x\tilde\mu(x)=1-x
  • I~(x)=1+x+x2+⋯=11−x\tilde I(x)=1+x+x^2+\dots=\frac{1}{1-x}
  • ε~(x)=1\tilde\varepsilon(x)=1
  • φ~(x)=1+(p−1)x+p(p−1)x2+p2(p−1)x3+⋯=1−x1−px\tilde\varphi(x)=1+(p-1)x+p(p-1)x^2+p^2(p-1)x^3+\dots=\frac{1-x}{1-px}
  • id~(x)=1+px+p2x2+⋯=11−px\tilde {id}(x)=1+px+p^2x^2+\dots=\frac{1}{1-px}
这些函数之间的狄利克雷卷积的结果即为对应生成函数乘积所对应的函数了。

四.莫比乌斯变换

  1. f(n)=∑d∣ng(d)  ⟺  g(n)=∑d∣nμ(d)f(nd)f(n)=\sum\limits_{d\mid n}g(d)\iff g(n)=\sum\limits_{d\mid n}\mu(d)f(\frac{n}{d})
  2. f(n)=∑d∣ng(d)  ⟺  g(n)=∑n∣dμ(nd)f(d)f(n)=\sum\limits_{d\mid n}g(d)\iff g(n)=\sum\limits_{n\mid d}\mu(\frac{n}{d})f(d)
  3. 反演结论：
  • ∑d∣nμ(d)=[n=1]\sum\limits_{d\mid n}\mu(d)=\left[n=1\right]
  • ∑d∣nφ(d)=n\sum\limits_{d\mid n}\varphi(d)=n
然后就是愉快的推式子环节了。
这块就先咕掉了。
因为主播都写在纸上了，没有时间转化成电子式子，并且用电脑推式子也很麻烦，有时间扫描成图片发一下吧，可能会放在别的地方。
题单：莫比乌斯反演典题

五.杜教筛

1.介绍

若要求积性函数 ff 的前缀和 sfsf。
找到一个积性函数 gg，考虑其狄利克雷卷积的前缀和
∑i=1n(f∗g)(i)=∑i=1n∑d∣if(d)g(id)=∑d=1ng(d)∑i=1⌊nd⌋f(i)=∑d=1ng(d)sf(⌊nd⌋)\begin{aligned} &\sum\limits_{i=1}^n(f\ast g)(i)\\ &=\sum\limits_{i=1}^n\sum\limits_{d\mid i}f(d)g(\frac{i}{d})\\ &=\sum\limits_{d=1}^n g(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\ &=\sum\limits_{d=1}^n g(d)sf(\lfloor\frac{n}{d}\rfloor) \end{aligned}
于是就有：g(1)sf(n)=∑i=1n(f∗g)(i)−∑i=2ng(i)sf(⌊ni⌋)g(1)sf(n)=\sum\limits_{i=1}^n (f\ast g)(i)-\sum\limits_{i=2}^n g(i)sf(\lfloor\frac{n}{i}\rfloor)
这个公式称为杜教筛公式。
如果构造得当，那么 ∑i=1n(f∗g)(i)\sum\limits_{i=1}^n (f\ast g)(i) 和 sg(n)=∑i=1ng(i)sg(n)=\sum_{i=1}^n g(i) d都是可以 O(1)O(1) 求出的。
具体的，我们设置一个函数 GS(n)GS(n) 求出 sf(n)sf(n) 的值，然后递归调用即可。
时间复杂度：O(n34)O(n^{\frac{3}{4}})
CPP
LL GS(int n){
	LL ans=fg_sum(n);
	for(LL l=2,r;l<=n;l=r+1){
		r=(n/(n/1));
		ans-=(g_sum(r)-g_sum(l-1))*GS(n\l);
	}
	return ans;
}

2.进一步优化

但这样可能优化的不是很多，所以我们再添加一些技巧来进一步优化。
先线性筛求出前 n23n^{\frac{2}{3}} 个答案，之后再用杜教筛，并配合记忆化，使得 GS(i)GS(i) 的每一个值都只计算一遍。
时间复杂度：O(n23)O(n^{\frac{2}{3}})

3.例题：求 μ\mu 和 φ\varphi 的前缀和

注意到 μ~(x)=1−x,I~(x)=1+x+x2+⋯=11−x\tilde\mu(x)=1-x,\tilde I(x)=1+x+x^2+\dots=\frac{1}{1-x}，其乘积 =1=ε~(x)=1=\tilde\varepsilon(x)
所以令函数 II 为杜教筛公式中的函数 gg。
则 ∑i=1n(f∗g)(i)=∑i=1nε(i)=1\sum\limits_{i=1}^n (f\ast g)(i)= \sum\limits_{i=1}^n \varepsilon(i)=1，sg(n)=∑i=1nI(i)=nsg(n)=\sum_{i=1}^n I(i)=n
这样，我们就可以在 O(n23)O(n^{\frac{2}{3}}) 的时间复杂度求出 ∑i=1nμ(i)\sum_{i=1}^n \mu(i) 了。
同理，求 φ\varphi 也是注意到 φ~(x)=1+(p−1)x+p(p−1)x2+p2(p−1)x3+⋯=1−x1−px,I~(x)=1+x+x2+⋯=11−x\tilde\varphi(x)=1+(p-1)x+p(p-1)x^2+p^2(p-1)x^3+\dots=\frac{1-x}{1-px},\tilde I(x)=1+x+x^2+\dots=\frac{1}{1-x}，其乘积 =11−px=id~(x)=\frac{1}{1-px}=\tilde {id}(x)
CPP
int n,m;
bool vis[N];
vector<int> pri;
LL phi[N],mu[N];
void pre(int n){
	phi[1]=mu[1]=1;
	for1(i,2,n){
		if(!vis[i]) pri.pb(i),phi[i]=i-1,mu[i]=-1;
		for(int j: pri){
			if(i>n/j) break;
			vis[i*j]=1;
			if(i%j==0){
				phi[i*j]=phi[i]*j;
				mu[i*j]=0;
				break;
			}
			phi[i*j]=phi[i]*phi[j];
			mu[i*j]=-mu[i];
		}
	}
	for1(i,2,n) phi[i]+=phi[i-1],mu[i]+=mu[i-1];
} 
unordered_map<int,LL> ans_phi;
unordered_map<int,int> ans_mu;
LL GS_phi(LL n){
	if(n<=(int)3e6) return phi[n];
	if(ans_phi.count(n)) return ans_phi[n];
	LL ans=1ll*n*(n+1)>>1ll;
	for(LL l=2,r;l<=n;l=r+1){
		r=(n/(n/l));
		ans-=1ll*(r-l+1)*GS_phi(n/l);
	}
	return ans_phi[n]=ans;
}
LL GS_mu(LL n){
	if(n<=(int)3e6) return mu[n];
	if(ans_mu.count(n)) return ans_mu[n];
	LL ans=1;
	for(LL l=2,r;l<=n;l=r+1){
		r=(n/(n/l));
		ans-=1ll*(r-l+1)*GS_mu(n/l);
	}
	return ans_mu[n]=ans;
}
int x;
void solve(){
	cin>>x;
	cout<<GS_phi(x)<<" "<<GS_mu(x)<<"\n";
	return ;
}

六、练习

好了，你已经学会莫反和杜教筛了，试着切掉以下这些水题吧。
求：∑i=1n∑j=1m[gcd⁡(i,j)=k]\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]
f(a,b,k)=∑t=1min⁡(a,b)μ(t)⌊atk⌋⌊btk⌋f(a,b,k)=\sum_{t=1}^{\min(a,b)}\mu(t)\lfloor \frac{a}{tk} \rfloor\lfloor \frac{b}{tk} \rfloor
ans=f(b,d,k)−f(b,c−1)−f(a−1,c)+f(a−1,c−1)ans=f(b,d,k)-f(b,c-1)-f(a-1,c)+f(a-1,c-1)
ans(k)=∑t=1nμ(t)⌊ntk⌋⌊ntk⌋ans(k)=\sum_{t=1}^n\mu(t)\lfloor \frac{n}{tk} \rfloor\lfloor \frac{n}{tk} \rfloor
求：∑i=1n∑j=1mgcd⁡(i,j)\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)
f(a,b)=∑t=1nφ(t)⌊nt⌋⌊nt⌋f(a,b)=\sum_{t=1}^n\varphi(t)\lfloor \frac{n}{t} \rfloor\lfloor \frac{n}{t} \rfloor
ans=2×f(a,b)−a×bans=2\times f(a,b)-a\times b
  • P2398 GCD SUM ans(a,b)=∑t=1nφ(t)⌊nt⌋⌊nt⌋ans(a,b)=\sum_{t=1}^n\varphi(t)\lfloor \frac{n}{t} \rfloor\lfloor \frac{n}{t} \rfloor
求：∑i=1n∑j=1mi×jgcd⁡(i,j)\sum_{i=1}^n\sum_{j=1}^mi\times j\gcd(i,j)
ans(n)=∑d=1nφ(d)d2sum3(⌊nd⌋)ans(n)=\sum_{d=1}^n\varphi(d)d^2sum^3(\lfloor\frac{n}{d}\rfloor)
求：∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)
ans(n,m)=∑T=1nT×sum1⌊nT⌋×sum1⌊mT⌋∑d∣Td×μ(d)ans(n,m)=\sum_{T=1}^nT\times sum^1{\lfloor\frac{n}{T}\rfloor}\times sum^1{\lfloor\frac{m}{T}\rfloor}\sum_{d\mid T}d\times\mu(d)
令 f(T)=∑d∣Td×μ(d)f(T)=\sum_{d\mid T}d\times\mu(d)
f(p)=1−p,f(pk)=f(p)f(p)=1-p,f(p^k)=f(p)
ans(n,m)=∑T=1nT×f(T)×sum1⌊nT⌋×sum1⌊mT⌋ans(n,m)=\sum_{T=1}^nT\times f(T)\times sum^1{\lfloor\frac{n}{T}\rfloor}\times sum^1{\lfloor\frac{m}{T}\rfloor}
求：∑i=1nlcm(i,n)\sum_{i=1}^n lcm(i,n)
ans(n)=n2(∑d∣nd×φ(d)+1)ans(n)=\frac{n}{2}(\sum_{d\mid n}d\times\varphi(d)+1)
令 g(T)=∑d∣Td×φ(d)g(T)=\sum_{d\mid T}d\times\varphi(d)
g(p)=1+p×(p−1),g(pk)=g(pk−1)+p2k−1(p−1)g(p)=1+p\times(p-1),g(p^k)=g(p^{k-1})+p^{2k-1}(p-1)
求：∑i=1n∑j=1md(i×j)\sum_{i=1}^n\sum_{j=1}^md(i\times j)
ans(n,m)=∑d=1nμ(d)∑i=1⌊nd⌋⌊ndi⌋∑j=1⌊md⌋⌊mdj⌋ans(n,m)=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{di}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dj}\rfloor
又有 ∑i=1nd(i)=∑j=1n⌊nj⌋\sum_{i=1}^nd(i)=\sum_{j=1}^n\lfloor\frac{n}{j}\rfloor
∴ans(n,m)=∑d=1nμ(d)∑i=1⌊nd⌋d(i)∑j=1⌊md⌋d(j)\therefore ans(n,m)=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}d(i)\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}d(j)
求：∏i=1n∏j=1mf(gcd(i,j)),f0=0,f1=1.fn=fn−1+fn−2,n≥2\prod_{i=1}^n\prod_{j=1}^mf(gcd(i,j)),f_0=0,f_1=1.f_n=f_{n-1}+f_{n-2},n\ge2
ans=∏T=1n(∏d∣Tf(d)μ(⌊Td⌋))⌊nT⌋⌊mT⌋ans=\prod_{T=1}^n(\prod_{d\mid T}f(d)^{\mu(\lfloor\frac{T}{d}\rfloor)})^{\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor} 内部的暴力预处理，外部数论分块。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...