莫比乌斯反演 引入 莫比乌斯反演是数论中的重要内容。对于一些函数 ,如果很难直接求出它的值,而容易求出其倍数和或约数和 ,那么可以通过莫比乌斯反演简化运算,求得 的值。
开始学习莫比乌斯反演前,需要先学习一些前置知识:数论分块 、狄利克雷卷积 。
莫比乌斯函数 定义 为莫比乌斯函数,定义为
含 有 平 方 因 子 为 的 本 质 不 同 质 因 子 个 数 详细解释一下:
令 ,其中 为质因子, 。上述定义表示:
时, ;对于 时:当存在 ,使得 时, ,也就是说只要某个质因子出现的次数超过一次, 就等于 ; 当任意 ,都有 时, ,也就是说每个质因子都仅仅只出现过一次时,即 , 中个元素唯一时, 等于 的 次幂,此处 指的便是仅仅只出现过一次的质因子的总个数。 性质 莫比乌斯函数不仅是积性函数,还有如下性质:
即 ,
证明 设
那么
根据二项式定理,易知该式子的值在 即 时值为 否则为 ,这也同时证明了 以及
注 这个性质意味着,莫比乌斯函数在狄利克雷生成函数中,等价于黎曼函数 的倒数。所以在狄利克雷卷积中,莫比乌斯函数是常数函数 的逆元。
补充结论 反演结论:
直接推导 :如果看懂了上一个结论,这个结论稍加思考便可以推出:如果 的话,那么代表着我们按上个结论中枚举的那个 是 ,也就是式子的值是 ,反之,有一个与 相同的值:
利用 函数 :根据上一结论, ,将 展开即可。
线性筛 由于 函数为积性函数,因此可以线性筛莫比乌斯函数(线性筛基本可以求所有的积性函数,尽管方法不尽相同)。
线性筛实现 拓展 证明
将 分解质因数:
首先,因为 是积性函数,故只要证明当 时 成立即可。
因为 是质数,于是
易知如下过程:
该式子两侧同时卷 可得
莫比乌斯变换 设 为两个数论函数。
形式一:如果有 ,那么有 。
这种形式下,数论函数 称为数论函数 的莫比乌斯变换,数论函数 称为数论函数 的莫比乌斯逆变换(反演)。
容易看出,数论函数 的莫比乌斯变换,就是将数论函数 与常数函数 进行狄利克雷卷积。
注 根据狄利克雷卷积与狄利克雷生成函数的对应关系,数论函数 的莫比乌斯变换对应的狄利克雷生成函数,就是数论函数 的狄利克雷生成函数与黎曼函数 的乘积。
形式二:如果有 ,那么有 。
证明 方法一:对原式做数论变换。
用 来替换 ,再变换求和顺序。最后一步变换的依据: ,因此在 时第二个和式的值才为 。此时 ,故原式等价于
方法二:运用卷积。
原问题为:已知 ,证明
易知如下转化: (其中 )。
对于第二种形式:
类似上面的方法一,我们考虑逆推这个式子。
我们把 表示为 的形式,然后把 的原定义代入式子。
发现枚举 再枚举 的倍数可以转换为直接枚举 的倍数再求出 ,发现后面那一块其实就是 , 整个式子只有在 的时候才能取到值。
问题形式 求值(多组数据)
根据容斥原理,原式可以分成 块来处理,每一块的式子都为
考虑化简该式子
因为 时对答案才用贡献,于是我们可以将其替换为 ( 当且仅当 时值为 否则为 ),故原式化为
将 函数展开得到
变换求和顺序,先枚举 可得
易知 中 的倍数有 个,故原式化为
很显然,式子可以数论分块求解。
时间复杂度
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr int N = 50000 ;
int mu [ N + 5 ], p [ N + 5 ];
bool flg [ N + 5 ];
void init () {
int tot = 0 ;
mu [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= N ; ++ i ) mu [ i ] += mu [ i - 1 ];
}
int solve ( int n , int m ) {
int res = 0 ;
for ( int i = 1 , j ; i <= min ( n , m ); i = j + 1 ) {
j = min ( n / ( n / i ), m / ( m / i ));
res += ( mu [ j ] - mu [ i - 1 ]) * ( n / i ) * ( m / i ); // 代推出来的式子
}
return res ;
}
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int T , a , b , c , d , k ;
init (); // 预处理mu数组
cin >> T ;
for ( int i = 1 ; i <= T ; i ++ ) {
cin >> a >> b >> c >> d >> k ;
// 根据容斥原理,1<=x<=b&&1<=y<=d范围中的答案数减去1<=x<=b&&1<=y<=c-1范围中的答案数和
// 1<=x<=a-1&&1<=y<=d范围中的答案数再加上1<=x<=a-1&&1<=y<=c-1范围中的答案数
// 即可得到a<=x<=b&&c<=y<=d范围中的答案数
// 这一步如果不懂可以画坐标图进行理解
cout << solve ( b / k , d / k ) - solve ( b / k , ( c - 1 ) / k ) -
solve (( a - 1 ) / k , d / k ) + solve (( a - 1 ) / k , ( c - 1 ) / k )
<< '\n' ;
}
return 0 ;
}
求值(多组数据)
易得原式即
将原式复制一份并且颠倒顺序,然后将 n 一项单独提出,可得
根据 ,可将原式化为
两个求和式中分母相同的项可以合并。
即
可以将相同的 合并在一起计算,故只需要统计 的个数。当 时, ,所以 的个数有 个。
故答案为
变换求和顺序,设 ,合并公因式,式子化为
设 ,已知 为积性函数,于是可以 筛出。每次询问 计算即可。
下面给出这个函数筛法的推导过程:
首先考虑 的值,显然它的约数只有 ,因此
又有 ,则原式可化为
于是有
那么,对于线性筛中的 ,令 ,可得
即
同理有
因此
时间复杂度 :
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 #include <iostream>
constexpr int N = 1000000 ;
int tot , p [ N + 5 ];
long long g [ N + 5 ];
bool flg [ N + 5 ]; // 标记数组
void solve () {
g [ 1 ] = 1 ;
for ( int i = 2 ; i <= N ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
g [ i ] = ( long long ) 1 * i * ( i - 1 ) + 1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= N ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
g [ i * p [ j ]] =
g [ i ] + ( g [ i ] - g [ i / p [ j ]]) * p [ j ] * p [ j ]; // 代入推出来的式子
break ;
}
g [ i * p [ j ]] = g [ i ] * g [ p [ j ]];
}
}
}
using std :: cin ;
using std :: cout ;
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int T , n ;
solve (); // 预处理g数组
cin >> T ;
for ( int i = 1 ; i <= T ; ++ i ) {
cin >> n ;
cout << ( g [ n ] + 1 ) * n / 2 << '\n' ;
}
return 0 ;
}
求值(对 取模)
易知原式等价于
枚举最大公因数 ,显然两个数除以 得到的数互质
非常经典的 式子的化法
后半段式子中,出现了互质数对之积的和,为了让式子更简洁就把它拿出来单独计算。于是我们记
接下来对 进行化简。首先枚举约数,并将 表示为
设 , ,显然式子可以变为
观察上式,前半段可以预处理前缀和;后半段又是一个范围内数对之和,记
可以 求解
至此
我们可以 数论分块求解 函数。
在求出 后,回到定义 的地方,可得原式为
可见这又是一个可以数论分块求解的式子!
本题除了推式子比较复杂、代码细节较多之外,是一道很好的莫比乌斯反演练习题!(上述过程中,默认 )
时间复杂度: (瓶颈为线性筛)
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr int N = 1e7 ;
constexpr int mod = 20101009 ;
int n , m , mu [ N + 5 ], p [ N / 10 + 5 ], sum [ N + 5 ];
bool flg [ N + 5 ];
int Sum ( int x , int y ) {
return (( long long ) 1 * x * ( x + 1 ) / 2 % mod ) *
(( long long ) 1 * y * ( y + 1 ) / 2 % mod ) % mod ;
}
int func ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) {
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( sum [ j ] - sum [ i - 1 ] + mod ) *
Sum ( x / i , y / i ) % mod ) %
mod ; //+mod防负数
}
return res ;
}
int solve ( int x , int y ) {
int res = 0 ;
int j ;
for ( int i = 1 ; i <= min ( x , y ); i = j + 1 ) { // 整除分块处理
j = min ( x / ( x / i ), y / ( y / i ));
res = ( res + ( long long ) 1 * ( j - i + 1 ) * ( i + j ) / 2 % mod *
func ( x / i , y / i ) % mod ) %
mod ; // !每步取模防爆
}
return res ;
}
void init () { // 线性筛
mu [ 1 ] = 1 ;
int tot = 0 , k = min ( n , m );
for ( int i = 2 ; i <= k ; ++ i ) {
if ( ! flg [ i ]) {
p [ ++ tot ] = i ;
mu [ i ] = -1 ;
}
for ( int j = 1 ; j <= tot && i * p [ j ] <= k ; ++ j ) {
flg [ i * p [ j ]] = true ;
if ( i % p [ j ] == 0 ) {
mu [ i * p [ j ]] = 0 ;
break ;
}
mu [ i * p [ j ]] = - mu [ i ];
}
}
for ( int i = 1 ; i <= k ; ++ i )
sum [ i ] = ( sum [ i - 1 ] + ( long long ) 1 * i * i % mod * ( mu [ i ] + mod )) % mod ;
}
int main () {
cin >> n >> m ;
init ();
cout << solve ( n , m ) << '\n' ;
}
多组数据,求
其中 , 表示 的约数个数
要推这道题首先要了解 函数的一个特殊性质
再化一下这个式子
将上述式子代回原式
那么 预处理 的前缀和, 分块处理询问,总复杂度 .
代码实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 #include <algorithm>
#include <iostream>
using namespace std ;
constexpr long long N = 5e4 + 5 ;
long long n , m , T , pr [ N ], mu [ N ], d [ N ], t [ N ],
cnt ; // t 表示 i 的最小质因子出现的次数
bool bp [ N ];
void prime_work ( long long k ) {
bp [ 0 ] = bp [ 1 ] = true , mu [ 1 ] = 1 , d [ 1 ] = 1 ;
for ( long long i = 2 ; i <= k ; i ++ ) { // 线性筛
if ( ! bp [ i ]) pr [ ++ cnt ] = i , mu [ i ] = -1 , d [ i ] = 2 , t [ i ] = 1 ;
for ( long long j = 1 ; j <= cnt && i * pr [ j ] <= k ; j ++ ) {
bp [ i * pr [ j ]] = true ;
if ( i % pr [ j ] == 0 ) {
mu [ i * pr [ j ]] = 0 ;
d [ i * pr [ j ]] = d [ i ] / ( t [ i ] + 1 ) * ( t [ i ] + 2 );
t [ i * pr [ j ]] = t [ i ] + 1 ;
break ;
} else {
mu [ i * pr [ j ]] = - mu [ i ];
d [ i * pr [ j ]] = d [ i ] << 1 ;
t [ i * pr [ j ]] = 1 ;
}
}
}
for ( long long i = 2 ; i <= k ; i ++ )
mu [ i ] += mu [ i - 1 ], d [ i ] += d [ i - 1 ]; // 求前缀和
}
long long solve () {
long long res = 0 , mxi = min ( n , m );
for ( long long i = 1 , j ; i <= mxi ; i = j + 1 ) { // 整除分块
j = min ( n / ( n / i ), m / ( m / i ));
res += d [ n / i ] * d [ m / i ] * ( mu [ j ] - mu [ i - 1 ]);
}
return res ;
}
int main () {
cin . tie ( nullptr ) -> sync_with_stdio ( false );
cin >> T ;
prime_work ( 50000 ); // 预处理
while ( T -- ) {
cin >> n >> m ;
cout << solve () << '\n' ;
}
return 0 ;
}
莫比乌斯反演扩展 结尾补充一个莫比乌斯反演的非卷积形式。
对于数论函数 和完全积性函数 且 :
我们证明一下
【 先 枚 举 乘 积 】 【 对 答 案 的 贡 献 为 , 于 是 省 略 】 【 是 完 全 积 性 函 数 】 【 】 【 当 且 仅 当 时 】 参考文献 algocode 算法博客
本页面最近更新:2023/10/4 21:50:08 ,更新历史 发现错误?想一起完善? 在 GitHub 上编辑此页! 本页面贡献者:ranwen , StudyingFather , 383494 , H-J-Granger , hyp1231 , iamtwz , Marcythm , Peanut-Tang , countercurrent-time , CyaceQuious , dkz051 , Early0v0 , Enter-tainer , ezoixx130 , FFjet , frank-xjh , GekkaSaori , Gesrua , Great-designer , guodong2005 , hehelego , Henry-ZHR , hjsjhn , hydingsy , i-yyi , Ir1d , kenlig , ksyx , Lcyanstars , Luckyblock233 , luojiny1 , MegaOwIer , Menci , mgt , mxr612 , NachtgeistW , nalemy , orzAtalod , ouuan , qwqAutomaton , SamZhangQingChuan , ShaoChenHeng , shawlleyw , Siyuan , Sshwy , sshwy , SukkaW , Tiphereth-A , UserUnauthorized , Vxlimo , WineChord , Xeonacid , yjl9903 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用