莫比乌斯反演
前置知识
积性函数
欧拉函数莫比乌斯函数
线性筛
数论分块
积性函数
指对于所有互质的整数a和b有f(ab)=f(a)f(b)的函数。
性质
1. 若 x = p 1 a 1 × p 2 a 2 . . . × p k a k , f ( x ) = f ( p 1 a 1 ) × f ( p 2 a 2 ) × . . . f ( p k a k ) 2. 如 果 两 个 函 数 f ( x ) , g ( x ) 均 是 可 乘 函 数 , 则 f ( x ) g ( x ) 也 是 可 乘 函 数 3. ∑ d ∣ n f ( d ) ∗ ∑ d ∣ m g ( d ) = ∑ d 1 ∣ n ∑ d 2 ∣ m f ( d 1 ) ∗ g ( d 2 ) 1.若x=p_1^{a_1}\times p_2^{a_2}...\times p_k^{a_k},f(x)=f(p_1^{a_1})\times f(p_2^{a_2})\times...f(p_k^{a_k})\\2.如果两个函数f(x),g(x)均是可乘函数,则f(x)g(x)也是可乘函数\\3.\sum_{d|n} f(d) * \sum_{d|m}g(d) = \sum_{d_1|n} \sum_{d_2|m}f(d_1) * g(d_2)
1 . 若 x = p 1 a 1 × p 2 a 2 . . . × p k a k , f ( x ) = f ( p 1 a 1 ) × f ( p 2 a 2 ) × . . . f ( p k a k ) 2 . 如 果 两 个 函 数 f ( x ) , g ( x ) 均 是 可 乘 函 数 , 则 f ( x ) g ( x ) 也 是 可 乘 函 数 3 . d ∣ n ∑ f ( d ) ∗ d ∣ m ∑ g ( d ) = d 1 ∣ n ∑ d 2 ∣ m ∑ f ( d 1 ) ∗ g ( d 2 )
欧拉函数
定 义 ϕ ( n ) = ∑ i = 1 n [ g c d ( i , n ) = = 1 ] 即 在 小 于 等 于 n 中 的 正 整 数 中 与 n 互 质 的 数 字 个 数 将 n 质 因 数 分 解 , n = p 1 a 1 × p 2 a 2 . . . × p k a k ϕ ( n ) = n ∗ ( 1 − p 1 ) ( 1 − p 2 ) . . . ( 1 − p k ) 定义\phi(n)=\sum_{i=1}^n[gcd(i,n)==1]\\
即在小于等于n中的正整数中与n互质的数字个数\\
将n质因数分解,n=p_1^{a_1}\times p_2^{a_2}...\times p_k^{a_k}\\
\phi(n)=n*(1-p_1)(1-p_2)...(1-p_k)
定 义 ϕ ( n ) = i = 1 ∑ n [ g c d ( i , n ) = = 1 ] 即 在 小 于 等 于 n 中 的 正 整 数 中 与 n 互 质 的 数 字 个 数 将 n 质 因 数 分 解 , n = p 1 a 1 × p 2 a 2 . . . × p k a k ϕ ( n ) = n ∗ ( 1 − p 1 ) ( 1 − p 2 ) . . . ( 1 − p k )
欧拉函数是积性函数
欧拉函数的线性筛求法
当 已 知 φ ( n ) 时 p 为 质 数 , φ ( n ∗ p ) 有 两 种 情 况 若 p ∣ n , φ ( n ∗ p ) = φ ( n ) ∗ p 否 则 ， φ ( n ∗ p ) = φ ( n ) ∗ ( p − 1 ) 当已知\varphi(n)时\\
p为质数,\varphi(n*p)有两种情况\\
若p|n,\varphi(n*p)=\varphi(n)*p\\
否则，\varphi(n*p)=\varphi(n)*(p-1)
当 已 知 φ ( n ) 时 p 为 质 数 , φ ( n ∗ p ) 有 两 种 情 况 若 p ∣ n , φ ( n ∗ p ) = φ ( n ) ∗ p 否 则 ， φ ( n ∗ p ) = φ ( n ) ∗ ( p − 1 )
原 理 如 下 记 n = p 1 ∗ p 2 ∗ . . . ∗ p k 接 下 来 讨 论 在 原 来 的 基 础 上 增 加 素 数 如 何 计 算 φ ( n ) = n ∗ ∏ ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) 假 如 加 了 一 个 素 数 q ， 如 果 出 现 过 φ ( n ∗ q ) = ( n ∗ q ) ∗ ∏ ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) 假 如 加 了 一 个 素 数 q ， 如 果 没 出 现 过 φ ( n ∗ q ) = ( n ∗ q ) ∗ ∏ ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) ( 1 − 1 q ) 原理如下\\
记 n = p_1 * p_2 * ... * p_k接下来讨论在原来的基础上增加素数如何计算\\\varphi(n) = n * \prod(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2})...(1 - \frac{1}{p_k}) \\假如加了一个素数 q，如果出现过\\\varphi(n * q) = (n * q) * \prod(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2})...(1 - \frac{1}{p_k}) \\假如加了一个素数 q，如果没出现过\\\varphi(n * q) = (n * q) * \prod(1 - \frac{1}{p_1}) (1 - \frac{1}{p_2})...(1 - \frac{1}{p_k}) (1 - \frac{1}{q}) \\
原 理 如 下 记 n = p 1 ∗ p 2 ∗ . . . ∗ p k 接 下 来 讨 论 在 原 来 的 基 础 上 增 加 素 数 如 何 计 算 φ ( n ) = n ∗ ∏ ( 1 − p 1 1 ) ( 1 − p 2 1 ) . . . ( 1 − p k 1 ) 假 如 加 了 一 个 素 数 q ， 如 果 出 现 过 φ ( n ∗ q ) = ( n ∗ q ) ∗ ∏ ( 1 − p 1 1 ) ( 1 − p 2 1 ) . . . ( 1 − p k 1 ) 假 如 加 了 一 个 素 数 q ， 如 果 没 出 现 过 φ ( n ∗ q ) = ( n ∗ q ) ∗ ∏ ( 1 − p 1 1 ) ( 1 − p 2 1 ) . . . ( 1 − p k 1 ) ( 1 − q 1 )
bj[1]=1;
phi[1]=1;
for(int i=2;i<=5e4;i++){
if(bj[i]==0){p[++k]=i;phi[i]=1;}
for(int j=1;j<=k&&i*p[j]<=5e4;j++){
bj[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
else
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
莫比乌斯函数
定 义 μ ( n ) = { 1 n = 1 ( − 1 ) k n 无 平 方 因 数 ， 记 n = p 1 ∗ p 2 ∗ . . . ∗ p k 0 n 有 平 方 因 数 定义
\mu(n) =
\begin{cases}
1 & n = 1 \\
(-1)^k & n无平方因数，记 n = p_1 * p_2 * ... * p_k \\
0 & n有平方因数
\end{cases}
定 义 μ ( n ) = ⎩ ⎪ ⎨ ⎪ ⎧ 1 ( − 1 ) k 0 n = 1 n 无 平 方 因 数 ， 记 n = p 1 ∗ p 2 ∗ . . . ∗ p k n 有 平 方 因 数
莫比乌斯函数为积性函数
莫比乌斯函数的线性筛求法
当 已 知 μ ( n ) 时 p 为 质 数 , μ ( n ∗ p ) 有 两 种 情 况 若 p ∣ n , μ ( n ∗ p ) = 0 否 则 ， μ ( n ∗ p ) = − μ ( n ) 当已知\mu(n)时\\
p为质数,\mu(n*p)有两种情况\\
若p|n,\mu(n*p)=0\\
否则，\mu(n*p)=-\mu(n)
当 已 知 μ ( n ) 时 p 为 质 数 , μ ( n ∗ p ) 有 两 种 情 况 若 p ∣ n , μ ( n ∗ p ) = 0 否 则 ， μ ( n ∗ p ) = − μ ( n )
bj[1]=1;
mu[1]=1;
for(int i=2;i<=5e4;i++){
if(bj[i]==0){p[++k]=i;mu[i]=-1;}
for(int j=1;j<=k&&i*p[j]<=5e4;j++){
bj[i*p[j]]=1;
if(i%p[j]==0){
mu[i*p[j]]=0;
break;
}
else
mu[i*p[j]]=-mu[i];
}
}
欧拉函数和莫比乌斯函数的关系
φ ( n ) n = ∑ d ∣ n μ ( d ) d \frac{\varphi(n)}{n} = \sum_{d|n} \frac{\mu(d)}{d}
n φ ( n ) = d ∣ n ∑ d μ ( d )
数论分块
求 解 ∑ i = 1 n [ n i ] 求解\sum_{i=1}^n[\frac n i]
求 解 i = 1 ∑ n [ i n ]
取n=11
[ 11 1 ] = 11 [\frac{11}{1}] = 11 [ 1 1 1 ] = 1 1
$[\frac{11}{2}] = 5 $
$[\frac{11}{3}] = 3 $
[ 11 4 ] = 2 , [ 11 5 ] = 2 [\frac{11}{4}] = 2, [\frac{11}{5}] = 2 [ 4 1 1 ] = 2 , [ 5 1 1 ] = 2
[ 11 6 ] = 1 , [ 11 7 ] = 1 , [ 11 8 ] = 1 , [ 11 9 ] = 1 , [ 11 10 ] = 1 , [ 11 11 ] = 1 [\frac{11}{6}] = 1, [\frac{11}{7}] = 1, [\frac{11}{8}] = 1, [\frac{11}{9}] = 1, [\frac{11}{10}] = 1, [\frac{11}{11}] = 1 [ 6 1 1 ] = 1 , [ 7 1 1 ] = 1 , [ 8 1 1 ] = 1 , [ 9 1 1 ] = 1 , [ 1 0 1 1 ] = 1 , [ 1 1 1 1 ] = 1
默认取下整，会有一段段的结果相同
当i小于等于n \sqrt n n n \sqrt n n
当i大于n \sqrt n n [ n n ] [\frac{n}{\sqrt n}] [ n n ] n \sqrt n n
故最多有2 n 2\sqrt n 2 n
我们只要求出每一段区间的左右端点即可
而每一段的左端点应是上一段的右端点+1
故我们只要能由该段左端点求出该段右端点即可
用l,r,分别表示区间左右端点
[ n r ] = [ n l ] [\frac n r]=[\frac n l] [ r n ] = [ l n ]
r = [ n [ n l ] ] r=[\frac{n}{[\frac n l]}] r = [ [ l n ] n ]
for(long long l=1,r;l<=b;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*(n/l)%mod;
ans%=mod;
}
f(x)为x的约数个数
容斥得∑ i = l r f ( i ) = ∑ i = 1 r f ( i ) − ∑ i = 1 l − 1 f ( i ) \sum_{i=l}^rf(i)=\sum_{i=1}^rf(i)-\sum_{i=1}^{l-1}f(i) ∑ i = l r f ( i ) = ∑ i = 1 r f ( i ) − ∑ i = 1 l − 1 f ( i )
我们只要解决∑ i = 1 n f ( i ) \sum_{i=1}^nf(i) ∑ i = 1 n f ( i )
显然可以转换为枚举每一个数是多少个数的约数∑ i = 1 n [ n i ] \sum_{i=1}^n[\frac n i] ∑ i = 1 n [ i n ]
数论分块即可
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long read(){
long long x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
int main(){
long long a,b,ans=0;
a=read()-1;b=read();
for(long long l=1,r;l<=b;l=r+1){
r=b/(b/l);
ans+=(r-l+1)*(b/l)%mod;
ans%=mod;
}
for(long long l=1,r;l<=a;l=r+1){
r=a/(a/l);
ans-=(r-l+1)*(a/l)%mod;
ans%=mod;
}
printf("%lld",(ans%mod+mod)%mod);
return 0;
}
接下来我们考虑这么一个式子如何数论分块，这也是莫比乌斯反演的题中经常要使用的
∑ i = 1 m i n ( n , m ) [ n i ] [ m i ] \sum_{i=1}^{min(n,m)}[\frac n i][\frac m i] ∑ i = 1 m i n ( n , m ) [ i n ] [ i m ]
上面我们已经分析过可以求出a \sqrt a a [ a i ] [\frac a i] [ i a ]
我们考虑对n , m n,m n , m n i \frac n i i n m i \frac m i i m
复杂度仍是O ( n ) O(\sqrt n) O ( n )
for(int l=1,r;l<=min(n,m);l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=(a/l)*(m/l);
}
莫比乌斯反演
核心式
约 数 式 ： 若 有 F ( n ) = ∑ d ∣ n f ( d ) 则 有 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) 倍 数 式 ： 若 有 F ( n ) = ∑ n ∣ d f ( d ) 则 有 f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) 约数式：\\
若有 \\
F(n) = \sum_{d|n}f(d) \\
则有 \\
f(n) = \sum_{d|n}\mu(d)F(\frac{n}{d}) \\
倍数式：\\
若有\\
F(n) = \sum_{n|d}f(d)\\
则有\\
f(n) = \sum_{n|d}\mu(\frac{d}{n})F(d)
约 数 式 ： 若 有 F ( n ) = d ∣ n ∑ f ( d ) 则 有 f ( n ) = d ∣ n ∑ μ ( d ) F ( d n ) 倍 数 式 ： 若 有 F ( n ) = n ∣ d ∑ f ( d ) 则 有 f ( n ) = n ∣ d ∑ μ ( n d ) F ( d )
∑ d ∣ n μ ( d ) F ( n d ) = ∑ d ∣ n μ ( d ) ∑ d 1 ∣ n d f ( d 1 ) 交 换 枚 举 次 序 ， 先 枚 举 d 1 = ∑ d 1 ∣ n f ( d 1 ) ∑ d ∣ n d 1 μ ( d ) 此 时 我 们 可 以 看 到 对 于 每 个 枚 举 的 d 1 ， 此 时 的 f ( d 1 ) 是 个 常 数 ， 从 而 ∑ d ∣ n d 1 μ ( d ) 仅 当 n d 1 = 1 时 有 非 零 值 为 1 此 时 d 1 = n 代 入 原 式 = f ( n ) ∗ 1 = f ( n ) ， 证 毕 \sum_{d|n}\mu(d)F(\frac{n}{d}) \\
= \sum_{d|n}\mu(d) \sum_{d_1 | \frac{n}{d}}f(d_1) \\
交换枚举次序，先枚举 d_1 \\
= \sum_{d_1|n}f(d_1) \sum_{d | \frac{n}{d_1}}\mu(d) \\
此时我们可以看到对于每个枚举的 d_1，此时的 f(d_1) 是个常数，从而 \\
\sum_{d | \frac{n}{d_1}}\mu(d) 仅当 \frac{n}{d_1} = 1时有非零值为 1 \\
此时 d_1 = n \\
代入原式 = f(n) * 1 = f(n)，证毕
d ∣ n ∑ μ ( d ) F ( d n ) = d ∣ n ∑ μ ( d ) d 1 ∣ d n ∑ f ( d 1 ) 交 换 枚 举 次 序 ， 先 枚 举 d 1 = d 1 ∣ n ∑ f ( d 1 ) d ∣ d 1 n ∑ μ ( d ) 此 时 我 们 可 以 看 到 对 于 每 个 枚 举 的 d 1 ， 此 时 的 f ( d 1 ) 是 个 常 数 ， 从 而 d ∣ d 1 n ∑ μ ( d ) 仅 当 d 1 n = 1 时 有 非 零 值 为 1 此 时 d 1 = n 代 入 原 式 = f ( n ) ∗ 1 = f ( n ) ， 证 毕
小结论
d ( x ) 表 示 x 的 约 数 个 数 d ( i ∗ j ) = ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = = 1 ] 简 单 证 明 ： 对 于 一 个 质 数 p , i 里 有 p a , j 里 有 p b ， 我 们 要 选 出 p k , 钦 定 做 出 如 下 选 择 若 k < = a , 在 i 中 选 出 p k , 若 k > a , 默 认 选 满 i 的 所 有 p ， 在 j 中 选 p k − a 按 照 这 样 的 选 法 能 不 重 不 漏 的 选 出 所 有 约 数 d(x)表示x的约数个数\\
d(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\\
简单证明：\\
对于一个质数p,i里有p^a,j里有p^b，我们要选出p^k,钦定做出如下选择\\
若k<=a,在i中选出p^k,若k>a,默认选满i的所有p，在j中选p^{k-a}\\
按照这样的选法能不重不漏的选出所有约数
d ( x ) 表 示 x 的 约 数 个 数 d ( i ∗ j ) = x ∣ i ∑ y ∣ j ∑ [ g c d ( x , y ) = = 1 ] 简 单 证 明 ： 对 于 一 个 质 数 p , i 里 有 p a , j 里 有 p b ， 我 们 要 选 出 p k , 钦 定 做 出 如 下 选 择 若 k < = a , 在 i 中 选 出 p k , 若 k > a , 默 认 选 满 i 的 所 有 p ， 在 j 中 选 p k − a 按 照 这 样 的 选 法 能 不 重 不 漏 的 选 出 所 有 约 数
求∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = = 1 ] \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)==1] ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = = 1 ]
把x,y往前提∑ x = 1 n ∑ y = 1 m [ n x ] [ m y ] [ g c d ( x , y ) = = 1 ] \sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][gcd(x,y)==1] ∑ x = 1 n ∑ y = 1 m [ x n ] [ y m ] [ g c d ( x , y ) = = 1 ]
开始莫比乌斯反演套路
记f ( k ) = ∑ x = 1 n ∑ y = 1 m [ n x ] [ m y ] [ g c d ( x , y ) = = k ] f(k)=\sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][gcd(x,y)==k] f ( k ) = ∑ x = 1 n ∑ y = 1 m [ x n ] [ y m ] [ g c d ( x , y ) = = k ]
F ( k ) = ∑ k ∣ d f ( d ) F(k)=\sum_{k|d}f(d) F ( k ) = ∑ k ∣ d f ( d )
则F ( k ) = ∑ x = 1 n ∑ y = 1 m [ n x ] [ m y ] [ k ∣ g c d ( x , y ) ] F(k)=\sum_{x=1}^n\sum_{y=1}^m[\frac n x][\frac m y][k|gcd(x,y)] F ( k ) = ∑ x = 1 n ∑ y = 1 m [ x n ] [ y m ] [ k ∣ g c d ( x , y ) ]
将k提出来
F ( k ) = ∑ x = 1 [ n k ] ∑ y = 1 [ m k ] [ n k x ] [ m k y ] [ 1 ∣ g c d ( x , y ) ] F(k)=\sum_{x=1}^{[\frac n k]}\sum_{y=1}^{[\frac m k]}[\frac n {kx}][\frac m {ky}][1|gcd(x,y)] F ( k ) = ∑ x = 1 [ k n ] ∑ y = 1 [ k m ] [ k x n ] [ k y m ] [ 1 ∣ g c d ( x , y ) ]
即F ( k ) = ∑ x = 1 [ n k ] ∑ y = 1 [ m k ] [ n k x ] [ m k y ] F(k)=\sum_{x=1}^{[\frac n k]}\sum_{y=1}^{[\frac m k]}[\frac n {kx}][\frac m {ky}] F ( k ) = ∑ x = 1 [ k n ] ∑ y = 1 [ k m ] [ k x n ] [ k y m ]
由莫比乌斯反演
f ( x ) = ∑ x ∣ d μ ( d x ) F ( x ) f(x)=\sum_{x|d}\mu(\frac d x)F(x) f ( x ) = ∑ x ∣ d μ ( x d ) F ( x )
故f ( 1 ) = ∑ d = 1 μ ( d ) F ( d ) = ∑ d = 1 μ ( d ) ∑ x = 1 [ n d ] ∑ y = 1 [ m d ] [ n d x ] [ m d y ] f(1)=\sum_{d=1}\mu(d)F(d)=\sum_{d=1}\mu(d)\sum_{x=1}^{[\frac n d]}\sum_{y=1}^{[\frac m d]}[\frac n {dx}][\frac m {dy}] f ( 1 ) = ∑ d = 1 μ ( d ) F ( d ) = ∑ d = 1 μ ( d ) ∑ x = 1 [ d n ] ∑ y = 1 [ d m ] [ d x n ] [ d y m ]
我们用数论分块预处理出g ( u , v ) = ∑ x = 1 u ∑ y = 1 v [ u x ] [ v y ] g(u,v)=\sum_{x=1}^u\sum_{y=1}^v[\frac u {x}][\frac v {y}] g ( u , v ) = ∑ x = 1 u ∑ y = 1 v [ x u ] [ y v ]
f ( 1 ) = ∑ d = 1 μ ( d ) g ( [ n d ] , [ m d ] ) f(1)=\sum_{d=1}\mu(d)g([\frac n d],[\frac m d]) f ( 1 ) = ∑ d = 1 μ ( d ) g ( [ d n ] , [ d m ] )
这个可以再一次数论分块
故复杂度O ( T n ) O(T\sqrt n) O ( T n )
#include<bits/stdc++.h>
using namespace std;
const int maxn=50005,maxm=50005;
int k=0;
int p[maxn],mu[maxn];
bool bj[maxn];
long long s[maxn];
int read(){
int x=0,y=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*y;
}
void pre(){
bj[1]=1;
mu[1]=1;
for(int i=2;i<=5e4;i++){
if(bj[i]==0){p[++k]=i;mu[i]=-1;}
for(int j=1;j<=k&&i*p[j]<=5e4;j++){
bj[i*p[j]]=1;
if(i%p[j]==0){
mu[i*p[j]]=0;
break;
}
else
mu[i*p[j]]=-mu[i];
}
}
for(int i=1;i<=5e4;i++)mu[i]+=mu[i-1];
for(int x=1;x<=5e4;x++){
long long res=0;
for(long long l=1,r;l<=x;l=r+1){
r=x/(x/l);
res+=(r-l+1)*(x/l);
}
s[x]=res;
}
}
int main(){
pre();
int t;
t=read();
while(t--){
int n,m;
n=read();m=read();
if(n>m)swap(n,m);
long long 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])*s[n/l]*s[m/l];
}
printf("%lld\n",ans);
}
return 0;
}
练习题
[POI2007]ZAP-Queries
[NOI2010]能量采集
[国家集训队]Crash的数字表格 / JZPTAB
按难度排序
总结
碰到莫比乌斯反演的题，把答案表示出来
强行套上gcd==x这样的一个判断形式
再设函数根据需要看是用莫比乌斯反演的约数式还是倍数式
然后用改变枚举顺序等方法化简式子，最后可能用到数论分块降低复杂度
