莫比乌斯反演
今天是世纪性的一天,因为我又又又又来看数论且弄懂了qwq。
前置知识: , (我们需要将式子化为整数分块可以解决的形式)
莫比乌斯函数
->
函数构成
- 当时,
- 当,且为互异质数时,;
(也就是就是分解质因数后,没有幂次大于2的质因子,此时函数值根据分解的个数决定)
- 只要含有任何质因子的幂次大于等于2,则
性质
- 对于任意正整数,
- 对于任意正整数,
code
版本,如果超时请去学杜教筛
云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
注意
的意思为b除以a为整数(b为a的倍数),即a能整除b
莫比乌斯反演
定理
和是定义在非负整数集合上的两个函数,它们之间满足关系
那么就有结论
这个定理即为莫比乌斯反演定理.
还有另外一种形式
若
则
证明
这里只给出第一种形式的证明,第二种形式同理.
由定理可设
//这一步没看懂的去看交换求和,接下来都为交换求和的知识点
//(莫比乌斯函数性质1)只有在时才有值,其他时候为0;
//因此
//故
得证.
例题
P2257 YY的GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
观察定理可知,我们在反演前需要设出与
而对于这种有的题目,一般套路为将设为的对数,将设为或n的倍数的对数;
(对数为满足条件的对数)
即有
带入反演公式后有
接下来开始计算答案
//反演
为了将消去,设
由于我们需要将式子向整除分块,即形如的形式
所以我们设
接下来就可以开始运算啦
为,即
为的前缀和,用来计算整除分块.
code
云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
标签:推导,乌斯,定理,反演,莫比,整除,com From: https://www.cnblogs.com/mouo/p/17770697.html