&!DOCTYPE html&
前言本文内容大部分来自Oier PoPoQQQ 的课件。
, ,密码:6ug5&/p&本文基本上由我学习相当于是制作的一篇学习笔记，但是将课件中的一些不完善的地方加以完善
使得更容易理解，加上了部分例题的代码引子介绍莫比乌斯反演之前我们先来看一个函数根据的定义于是我们便可以通过推导出在推导的过程中我们是否发现了一些规律?莫比乌斯反演莫比乌斯反演
莫比乌斯反演定义
其中为莫比乌斯函数[1]，定义如下
莫比乌斯函数的定义式
莫比乌斯函数的性质
当n不等于1时，n所有因子的莫比乌斯函数值的和为0，\
当的时候显然成立当时质因子个数为的因子只有个接下来只需证明即可因为二项式定理令代入即可得证。
只需要令，代入即可那么就有为什么成立？
积性函数 数论上积性函数的定义\
设函数其中对于任意都有则称为一个积性函数；若对于任意都有则称为一个完全积性函数。
积性函数的性质\
积性函数的前缀和也是积性函数\
因为积性函数是积性函数,
因此可以通过线性筛求出莫比乌斯函数的值
for(i=2;i&=n;i++){
if(!not_prime[i]){
prime[++tot]=i;
for(j=1;prime[j]*i&=n;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0){
mu[prime[j]*i]=0;
mu[prime[j]*i]=-mu[i];
题目大意：求第k个无平方因子数\
首先二分答案，问题转化为求之间有多少个无平方因子数\
根据容斥原理可知，对于之内所有的质数，
答案G(x)=0个质数平方倍数的个数-1个质数平方倍数的个数+2个质数平方倍数的个数-...，
那么对于偶数个质数平方对于答案的贡献就是正的，否则是负的，\
如果不是若干个互异质数的乘积，那么对答案没有影响，
如何表示这个式子呢?\
观察莫比乌斯函数的定义[1]，可以知道对于能对答案产生贡献的数，，其中为分解得到质数的个数
根据上述说明，那么可以得知结果\
#include&iostream&
#include&cstdio&
#include&cmath&
#define N 100005
bool not_prime[N];
int prime[N];
int mu[N];
void Mu(int n){
for(i=2;i&=n;i++){
if(!not_prime[i]){
prime[++tot]=i;
for(j=1;prime[j]*i&=n;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0){
mu[prime[j]*i]=0;
mu[prime[j]*i]=-mu[i];
int can(int x){
int sum=0;
int s=floor(sqrt(x));
for(int i=1;i&=s;++i)
sum+=mu[i]*floor(x/(i*i));
int main(){
Mu(N);int T,
scanf("%d",&T);
while(T--){
scanf("%d",&num);
long long l=1,r=num&&1,
while(l&r){
mid=(l+r)&&1;
if(can(mid)&num)
printf("%lld\n",r);
莫比乌斯反演定理的证明
证明同理，一般要用到的都是这种形式
莫比乌斯反演的应用
对于一些函数,如果我们很难直接求出它的值，而容易求出倍数和或约数和,
那么我们可以直接利用莫比乌斯反演来求得的值
f(n)表示某一范围内(x,y)=n的数对的数量，\
F(n)表示某一范围内n|(x,y)的数对的数量\
那么直接求f(n)并不是很好求，而F(n)求起来相对无脑一些，\
那么我们可以通过对F(n)进行莫比乌斯 反演来求得f(n)\
题目大意：询问有多少对满足且。
根据容斥原理，这个题目就可以转化成
其中答案为\
那么我们需要快速求出
这个式子可以进一步转化为
考虑莫比乌斯反演, 令
反演后可得
分析可知这个算法的复杂度是
我们还需要对这个算法进行进一步优化
因为至多只有个取值，
那么至多只有个取值
因为使得成立的值都是连续的，
所以可以维护一个莫比乌斯函数的前缀和，
这样就可以在的时间内出解
枚举除法的取值在莫比乌斯反演的应用当中非常常用
if(a&b)swap(a,b);
for(i=1;i&=a;i=last+1){
last=min(a/(a/i),b/(b/i));
re+=(a/i)*(a/i)*(sum[last]-sum[i-1]);
代码异常好写
#include&iostream&
#include&cstdio&
#include&cmath&
#define N 50005
#define inf 0x7fffffff
bool not_prime[N];
int prime[N];
int sum[N];
int mu[N];
void Mu(int n){
for(i=2;i&=n;i++){
if(!not_prime[i]){
prime[++tot]=i;
for(j=1;prime[j]*i&=n;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0){
mu[prime[j]*i]=0;
mu[prime[j]*i]=-mu[i];
for(int i=1;i&=n;++i)
sum[i]=sum[i-1]+mu[i];
int ans(int n,int m){
if(n&m)swap(n,m);
int last,i,re=0;
for(i=1;i&=n;i=last+1){
last=min(n/(n/i),m/(m/i));
re+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
int main(){
int a,b,c,d,k;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
a/=k;b/=k;c/=k;d/=k;
int Ans=ans(b,d)-ans(a,d)-ans(b,c)+ans(a,c);
printf("%d\n",Ans);
BZOJ 10s但是luogu却莫名WA\
全部加上long long 之后总算是过了\
百思不得其解
题目大意：求有多少数对满足满足为质数
阅读(...) 评论()在讲这个函数之前。最好先了解欧拉函数。
我们用 \ &记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。
欧拉函数用来表示。
那么根据法里级数的展开(这个感觉和ACM关系不大就先不介绍了。大概讲的就是构造所有最简分数的一种树。而法里级数n定义分母&=n的最简分数。)
比如对于分母为12.
1/12 &1/6 & &1/4 & 1/3 & 5/12 & 1/2 & 7/12 & 2/3 & 3/4 & 5/6 & 11/12 1/1
观察这些式子。你会发现分母都是能整除12的.也就是说分母为d。 &d\m
分母为1的集合 1/1&
分母为2的集合 1/2
分母为3的集合 1/3 &2/3
分母为4的集合 1/4 &3/4
分母为6的集合 1/6 &5/6
分母为12的集合 1/12 5/12 7/12 11/12
会发现对于每个m的除数(也就是分母啦)的集合的分子都是和分母是互素的。并且穷举了。
比如4 & 1 和 3 是和4互素的。
1+1+2+2+2+4 = 12 (其实这里是废话！在推导中间就能得到了。因为我们列了12个分式嘛，重点在于是穷举了每个除数的互素数。)
不过我们可以从这得到一个和式:
重点在于这个形式的公式：
有一个结论:如果f(d) 让g(m)是积性函数。那么f(d) 是积性函数（这个结论很重要。）
同时如果我们能够证明这个结论的话。也可以通过这个结论去证明欧拉函数的积性。
因为根据上面我们推出的和式。对于欧拉函数的对应g(m)为m.m明显是积性的函数。
如果我们的结论成立。那么欧拉函数是积性的。(这里的积性不代表完全积性。我们知道欧拉函数的积性必须两个数互素的情况下才有。)
&因为g(m)为积性函数，所以有：
扩展左边：
如果进一步细分左边和右边。会发现左边是
若该等式对于任意m恒成立.那么
根据上面的等式的话就是一个项一个项对应起来。而从这也能看出其逆命题也是正确的。就是当f(d) 为积性函数的时候 g(m)也为积性函数。
在此，欧拉函数的积性就算证明成功了。
对于上述的研究似乎没有提到莫比乌斯函数。但是以上的研究是贯彻整个莫比乌斯函数的。包括其积性的证明。和反演。
思考一个这样的问题：
　　& & & & & & & &对比 & & &&
　　欧拉函数是比较复杂的。而其对应的g(m) 是简单的。为m。
　　我们是否可以通过g(m)的函数能够获得f(m)的函数呢?(这里f(m)自变量变成m了。不过小小思考后明显不用在意。)
　　而我们有这样的一个反演原理：
　　 其中为莫比乌斯函数。
　　莫比乌斯函数满足一个极其重要的性质。或者说是因为这个性质而定义了这个函数！
　　其中 [m=1]代表m=1的时候为1. m不等于1的时候为0
　　这个性质很神奇。但是却又不神奇。因为其实是认为构造出有这样的性质。使得莫比乌斯反演得以成立。
　　但是我们要计算其反演后的结果。我们又不得不知道具体的的值如何。其值我们先放着。先证明反演：
　　证明反演之前有两个步骤最好先需要有预备知识：
　　这个其实思考一下就知道了。我们不过就是把计算顺序发生了改变。
　　这个和式确实看起来复杂。而且我是直接搬其证明过程中遇到的这个和式。
不过我们从一个例子上去理解:
　　对于m = 12来说:　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　&　　
1 2 3 4 6 12
　&&(12)f(1)
　　&(6)f(1)+&(6)f(2)
　　&(4)f(1)+　　　　 &&(4)f(3)
　　&(3)f(1)+&(3)f(2)+　　　　 &&(3)f(4)
　　&(2)f(1)+&(2)f(2)+&(2)f(3)+　　　　 &&(2)f(6)
　　&(1)f(1)+&(1)f(2)+&(1)f(3)+&(1)f(4)+&(1)f(6)+&(1)f(12)
-----------------------------------------------------------------------------&
& & & & & & & & & & & & & &明显的求这个式子之和。
我们的排列是以&的自变量排列的。那假如按f的自变量(k)进行排列呢? 我们上面的式子竖着都已经对应好了。
不难得出下表:(不根据式子。直接跟上)　　　　　　
12 6 4 2 1
1 2 3 4 6 12
细心对比上表：
1 2 3 4 6 12
&会发现有意思的是m/d和k换了个位置而已。其实这并不是巧合。但是这并不是重点。
我们要用一个式子描述出这种情形。其实我们不过是把式子处理成以k为规整的。
而描述成和式其实就是上述恒等式的右边：
值得注意的是 d 已经不是原来的d了。只是一个从1开始的循环量而已。一旦满足d\(m/k) 就有意义。所以我本来第2个表不想统计d的。不过最后还是统计了。出于容易研究吧。
因为我们还得一点细节才能解释这个恒等式右边的表达式。
所以对于指定的k,d的集合为k的倍数。
设l = m/d. (这里的l就是上述表达式的d!)
也就是我们要证明指定k 那么l的集合为 l\(m/k)
l = m/nk. n为整数。 (m/k) / l &= n 所以l\(m/k).得证。
也许我的证明有点繁琐。如果你一眼看出来。那也没事。
其实就是寻找指定k &m/d应该满足怎么样的条件。 其中k\d且d\m。
有了这2个恒等式我们可以接下来证明莫比乌斯反演:
证明过程：
其反证类似的。具体数学中的习题啊。也当作大家的习题好了。
就是第二个恒等式。具体数学中是分了2步。那个用拉斐尔证明的4.9虽然说原理并不难。但是具体数学上用得简直有点出神入化让我有点摸不着头脑。
之后一步是利用第一个恒等式然后证出上述的第二个恒等式。
让我们看看&具体是一个什么样的函数。
首先:[m=1]这个函数是积性的。所以&(d)这个函数必然也是积性的。利用我们一开始证明的那个结论。
&也就是说要求&(m).我们只要计算&(p^k). 根据算术基本定理理所当然的。且p代表素数。
根据其性质:
那么有 &(1)+ &(p^1) + &(p^2) + &(p^3)+...&(p^k) = [p^k=1].
假如p = 1.(其实1不是素数，我们这样的假设是不成立的，这里只是为了运算出&(1))
那么。 &(1)= 1.
假如p ！= 1.
那么&&(1)+&&(p^1) +&&(p^2) +&&(p^3)+...&(p^k) = 0.
&(1)+&&(p^1) = 0&
可知&(p^1)=&(p)= -1.
&&(1)+&&(p^1) +&&(p^2) = 0 .
&即&(p^2) &= 0
&(p^(3~k)) = 0
也就是说。
&(1) = 1 ,&&(p) = -1 &,&&(p^k) &= 0 &(k&=2)
推广到 m:（m为任意实数）
下面0的情况。是存在p^2整除m.也就是m存在p^2因子的时候。
&注意:&(1) = 1
好了。反演和莫比乌斯的函数我们都理解透彻了。具体应用可以看
阅读(...) 评论()莫比乌斯反演
莫比乌斯反演是数论数学中很重要的内容，可以用于解决很多组合数学的问题。
莫比乌斯函数
莫比乌斯函数，数论函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯首先使用μ(n)作为莫比乌斯函数的记号。
莫比乌斯函数是指以下的函数：
在这里，λ(n)是刘维尔函数
莫比乌斯函数是一个数论函数，它同时也是一个积极函数（μ(ab) =μ(a)μ(b), a,b互质 ）
当n不等于1时，n的所有因子的莫比乌斯函数值的和为0
莫比乌斯函数完整定义的通俗表达：
1、莫比乌斯函数μ(n)的定义域是N
2、μ(1)=1
3、当n存在平方因子时，μ(n)=0
4、当n是素数或奇数个不同素数之积时，μ(n)=-1
5、当n是偶数个不同素数之积时，μ(n)=1
莫比乌斯反演的引入
莫比乌斯反演是数论中的重要内容，在许多情况下能够简化运算。我们考虑以下和函数：
d|n意思是d是n的因子
我们需要找到f(n)和F(n)之间的关系。从和函数定义中可以看出：
F(2)=f(1)+f(2)
F(3)=f(1)+f(2)+f(3)
F(4)=f(1)+f(2)+f(4)
F(5)=f(1)+f(5)
F(6)=f(1)+f(2)+f(3)+f(6)
F(7)=f(1)+f(7)
F(8)=f(1)+f(2)+f(4)+f(8)
F(9)=f(1)+f(3)+f(9)
那么我们就可以推出：
f(2)=F(2)-F(1)
f(3)=F(3)-F(1)
f(4)=F(4)-F(2)
f(5)=F(5)-F(1)
f(6)=F(6)-F(3)-F(2)-F(1)
f(7)=F(7)-F(1)
f(8)=F(8)-F(4)
f(9)=F(9)-F(3)
从中我们可以看出，若n=p^2(p为质数)，那么，F(p)=f(1)+f(p)，F(n)=f(1)+f(p)+f(p^2)，所以，f(n)=F(P^2)-F(P).
如果我们要函数满足：
那么通过上边推导，我们可以知道μ(p^2)=0所以我们猜测：
莫比乌斯反演定理
设f(n)和g(n)是定义在正整数集合上的两个函数。定义如下：
莫比乌斯函数μ(d)定义
若d=1，那么μ(d)=1
若d=p1p2……pk (k为不同质数，且次数都为一)，μ(d)=(-1)^k
其余 μ(d)=0
莫比乌斯反演的性质
性质一 （莫比乌斯反演公式）：
性质二：μ(n)为积极函数
性质三：设f是算术函数，它的和函数
是积极函数，那么f也是积极函数
莫比乌斯函数ACM
莫比乌斯入门请耐心往下看：
OK.现在可以开始刷题了。
莫比乌斯反演
HDU 1695 GCD
从区间[1, b]和[1,d]中分别选一个x, y，使得gc...
莫比乌斯函数打表
莫比乌斯反演推荐博客：
莫比乌斯详解，莫比乌斯应用
莫比乌斯函数是莫比乌斯反演的核心
莫比乌斯函数打表
void getMu(){
莫比乌斯函数
莫比乌斯函数
莫比乌斯反演
莫比乌斯函数值：
int mobi(int n)
for(int i=2;i*i
莫比乌斯函数详解
在讲这个函数之前。最好先了解欧拉函数。
记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。
欧拉函数用来表示。
那么根据法里级数的展开(这个感觉和A...
莫比乌斯反演
答：欧几里得
int gcd(int a,int b)
return b==0?a:gcd(b,a%b);
这段gcd代码大家一定很熟悉^_^。gcd嘛...
一、莫比乌斯函数(M?bius function)是指以下的函数：
在这里，λ(n)是刘维尔函数
莫比乌斯函数是一个数论函数，它同时也是一个积性函数(i.e.μ(ab) =μ(a)μ(b), ...
莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。（据说，高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数）。
1244 莫比乌斯函数之和
基准时间限制：3 秒 空间限制：131072 KB 分值: 320 难度：7级算法题 收藏
莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(M...
没有更多推荐了，在数论中的积性函数：对于正整数n的一个算术函数 f(n)，若f(1)=1，且当a,b时f(ab)=f(a)f(b)，在数论上就称它为积性函数。若对于某积性函数 f(n)
，就算a, b不互质，也有f(ab)=f(a)f(b)，则称它为完全积性的。
φ(n) －，计算与n互质的正整数之数目
μ(n) －，关于非平方数的质因子数目
莫比乌斯函数完整定义的通俗表达：
1）莫比乌斯函数μ(n)的定义域是N
2）μ(1)=1
3）当n存在平方因子时，μ(n)=0
4）当n是素数或奇数个不同素数之积时，μ(n)=-1
5）当n是偶数个不同素数之积时，μ(n)=1
莫比乌斯函数，数论函数，由德国数学家和天文学家莫比乌斯(August Ferdinand M&bius ,)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而据说，高斯(Gauss)比莫比乌斯早三十年就曾考虑过这个函数。莫比乌斯函数在数论中有着广泛应用。
设f为算术函数，F为f的和函数，有F(n)=sigma[f(d)]，d|n。我们现在要做的事是如何根据F求出f。
F(2)=f(1)+f(2)
F(3)=f(1)+f(3)
F(4)=f(1)+f(2)+f(4)
F(5)=f(1)+f(5)
F(6)=f(1)+f(2)+f(3)+f(6)
F(7)=f(1)+f(7)
F(8)=f(1)+f(2)+f(4)+f(8)
利用解方程，我们得到：
f(2)=F(2)-F(1)
f(3)=F(3)-F(1)
f(4)=F(4)-F(2)
f(5)=F(5)-F(1)
f(6)=F(6)-F(3)-F(2)+F(1)
f(7)=F(7)-F(1)
f(8)=F(8)-F(4)
观察发现，f(n)等于形式为+/-F(n/d)，d|n，所以我们推论出莫比乌斯反演公式：
f(n)=sigma[u(d)*F(n/d)](一定要记住这个形式呀，否则后面你就不好理解了)。
现在试着确定u函数：
例如，对于上面的例子有u(1)=u(6)=1, u(2)=u(3)=u(5)=u(7)=-1，u(4)=u(8)=0。
继续观察：
F(p)=f(1)+f(p)=&f(p)=F(p)-F(1)，那么u(p)=-1。
继续观察：
F(p^2)=f(1)+f(p)+f(p^2)=&f(p^2)=F(p^2)-(F(p)-F(1))-F(1)=F(p^2)-F(p),这又有u(p^2)=0。
同理我们推出f(p^3)=F(p^3)-F(p^2)，这又有u(p^3)=0，就这样推下去，我们有当k&1，有u(p^k)=0。
继续观察：
设p1，p2为素数
F(p1*p2)=f(p1*p2)+f(p1)+f(p2)+f(1)=&f(p1*p2)=F(p1*p2)-F(p1)-F(p2)+F(1)。
这里有u(1)=1, u(p2)=-1,u(p1)=-1,u(p1*p2)=1。
如果不嫌累，你就在继续推，以下直接给出莫比乌斯函数了（要是一一列举得累死我）。
u(n) = 1 如果n=1
= (-1)^r 如果n=p1*p2*......pr，其中pi为各不相同的素数
行了，莫比乌斯函数有很多性质呢。就不证明了，只给出这些性质吧。
(1)莫比乌斯函数是乘性函数
(2)设F(n)=sigma[u(d)]，d|n，如果n=1，则F(n)=1，若n&1则等于0。
至于如何去验证莫比乌斯函数确实能够达到反演的大家就自己研究吧。
并且若f的和函数F是乘性的，我们可以根据莫比乌斯反演推出f也是乘性的。
好了，看看利用莫比乌斯反演公式能得到什么好玩的。
设f1(n)=n，f2(n)=1
F1(n)=sigma(f1(d)), d|n1
F2(n)=sigma(f2(d)), d|n2
那么根据反演公式有
n=sigma[u(n/d)*F1(d)]
1=sigma[u(n/d)*F2(d)]
很神奇，是吧。
若f是欧拉函数，则f(n)=n*(sigma[u(d)/d]),d|n。
今天终于把莫比乌斯看明白了，但证明貌似还是无力。
设f(d) 表示gcd为d的倍数的数的对数
g(d)表示gcd恰好为d的数的对数
f(d) = ∑ g(n) (n % d == 0)
mu[n / d] * f(n) (n %d == 0)
上面两个式子就是套路，没啥难的
所以 g(1) = ∑mu[n] * f(n)
求一下mu[ ]，枚举一下n就可以AC了
方法一：莫比乌斯反演
#include&iostream&
#include&cstdio&
#include&cstring&
#include&algorithm&
const int maxn=222232;
int mu[maxn],a[maxn],prime[maxn],cnt[maxn],num[maxn];
bool vis[maxn];
void mobius(int N)
vis[1]=mu[1]=1;
for(int i=2;i&=N;i++)
if(!vis[i])
prime[pnum++]=i;
for(int j=0;j&j++)
if(i*prime[j]&N)
vis[i*prime[j]]=1;//筛掉合数
if(i%prime[j]==0)
mu[i*prime[j]]=0;
//保证合数使用最小的素数筛掉的
mu[i*prime[j]]=-mu[i];
int main()
//freopen("in.txt","r",stdin);
mobius(222222);
while(scanf("%d",&n)!=EOF)
int max1=0;
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(cnt));
for(int i=1;i&=n;i++)
scanf("%d",&a[i]);
num[a[i]]++;
max1=max(max1,a[i]);
for(int i=1;i&=max1;i++)
for(int j=i;j&=max1;j+=i)
cnt[i]+=num[j];
long long ans=0;
for(int i=1;i&=max1;i++)
ans+=((long long)cnt[i]*(cnt[i]-1)/2)*mu[i];
printf("%lld\n",ans);
方法二：跟莫比乌斯阿反演差不多，只不过是把它的倍数中重复计算的去掉了
#include&iostream&
#include&cstdio&
#include&cstring&
typedef long long LL;
const int maxn=222232;
int cnt[maxn],n,x,max1;
LL ans[maxn];
void solve()
//memset(ans,0,sizeof(ans));
for(int i=2;i&=max1;i++)
for(int j=i;j&=max1;j+=i)ans[i]+=cnt[j];
for(int i=2;i&=max1;i++)ans[i]=ans[i]*(ans[i]-1)/2;
for(int i=max1;i&1;i--)
for(int j=2*i;j&=max1;j+=i)
ans[i]-=ans[j];//把重复计算的去掉
for(int i=2;i&=max1;i++)sum+=ans[i];
sum=(LL)n*(n-1)/2-
printf("%lld\n",sum);
int main()
while(scanf("%d",&n)!=EOF)
memset(cnt,0,sizeof(cnt));
for(int i=0;i&n;i++)
scanf("%d",&x);
max1=max(max1,x);
莫比乌斯函数的证明
遗忘是可怕的东西……好记性不如烂笔头讲真……命题现在假设我不知道什么是莫比乌斯函数，只知道F(x)=∑d∣xf(d)F(x)=\sum_{d\mid x}f(d)若已知F(x)F(x)，求f(x)f(...
莫比乌斯函数详解
在讲这个函数之前。最好先了解欧拉函数。
记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。
欧拉函数用来表示。
那么根据法里级数的展开(这个感觉和A...
SPOJ-SQFREE SPOJ4168 莫比乌斯函数の性质
//题意：SPOJ-SQFREE，SPOJ内有多少个无平方因子数
//思路：莫比乌斯函数的性质。。实际上就是mu[i]^2的前缀和S
//然而直接搞会超时，S有Osqrtn的求法。公...
莫比乌斯函数学习笔记
e(n)=?1 n=10 n≠1e(n)=\lgroup^{1\ n=1}_{0\ n\neq1}
I(n)=1I(n)=1
id(n)=nid(n)=n
σ0(n)因子个数\...
在讲这个函数之前。最好先了解欧拉函数。我们用 \
记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。欧拉函数用来表示。
那么根据法里级数的展开(这个感觉和ACM关系...
莫比乌斯函数和莫比乌斯反演莫比乌斯函数数论函数：定义域为正整数、陪域为复数的函数，下面讨论的函数均为数论函数。
莫比乌斯函数μ(d)\mu(d)：
- 若d=1d=1，μ(d)=1\mu(d)=1...
一、莫比乌斯函数(M?bius function)是指以下的函数：
在这里，λ(n)是刘维尔函数
莫比乌斯函数是一个数论函数，它同时也是一个积性函数(i.e.μ(ab) =μ(a)μ(b), ...
莫比乌斯函数，数论中的战斗机
莫比乌斯函数，数论函数，由德国数学家和天文学家莫比乌斯(August Ferdinand M&bius ,)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的...
莫比乌斯函数ACM
莫比乌斯入门请耐心往下看：
OK.现在可以开始刷题了。
莫比乌斯反演
HDU 1695 GCD
从区间[1, b]和[1,d]中分别选一个x, y，使得gc...
莫比乌斯函数和反演定理的理解
这几天复习了莫比乌斯函数的运用，主要是用来解决倍数的问题的。现在就谈谈莫比乌斯函数的性质和反演定理的理解。
首先定义 u(x)u(x) 为莫比乌斯函数。他有以下性质:
1.∑d|mu(x)=[m=...
没有更多推荐了，遗忘是可怕的东西……好记性不如烂笔头讲真……
现在假设我不知道什么是莫比乌斯函数，只知道F(x)=∑d∣xf(d)若已知F(x)，求f(x)的表达式。
从已知的关系，可以得到性质：
1. 若y|x(y&x)，则F(y)包含的所有f(d)都被F(x)包含了，F(y)不能包含f(x)
2. 包含f(x)的最小项是F(x)
记x的第i小的约数是yi(yi&x)，共有k个约数，则f(x)=F(x)-∑1≤i≤kf(yi)由于左边的f(x)是一次的，所以右边是F(yi)的线性组合，设ai作为F(yi)的系数，即f(x)=F(x)+∑1≤i≤kaiF(yi)=F(x)+∑1≤i≤kbif(yi)可知所有的bi=-1.现在即要求解ai.
从yk，即x的最大真约数开始解，只有F(yk)包含了f(yk)，可得ak=-1。同时对所有f(yk的约数)前的系数都贡献-1。
再看yk-1，如果f(yk-1)前的系数已经被贡献了-1，则ak=0，看下一个约数；否则要令当前的贡献值+ak-1=-1，由此确定ak-1
举个例子：x=180,{yi}={1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90}
先确定90的系数a17为-1，前面是90的约数的系数添上-1；
再看60的列和为0，故a16为-1，前面是6的约数的系数添上-1；
再看45的列和为-1，故a15为0；
直到所有系数都确定如下表：使得每列之和都为-1，即f(yi)前的系数都为-1
逐步求解的过程比较长，有没有什么关于ai的性质呢？
假设已经现在正在求ai，其列和由已经确定的aj(j&i)决定，且只有当yi|yj时，才会对f(yi)做非零标记。
设p为素数，若xyi=p，则说明没有满足的j，确定ai=-1；
若xyi=p1p2，则有xyj=p1或p2的yj已经先行对f(yi)做了两次-1标记，则确定ai=+1；
若xyi=p1p2...ps，则已有标记为-C1s+C2s-C3s...+(-1)s-1Cs-1s=∑i=0sCis(-1)i-C0s-(-1)sCss=(1-1)s-1-(-1)s=-1-(-1)s则确定ai=(-1)s；
若xyi=pv11pv22...pvss且至少有一个v大于1，则已有标记为-C1s+C2s-C3s...+(-1)sCss=∑i=0sCis(-1)i-C0s=(1-1)s-1=-1则确定ai=0
由此可以确定f(x)=F(x)+∑1≤i≤kaiF(yi)所有的系数ai如下：
ai={(-1)s0xyi=p1p2...ps,其中ps为不同的素数xyi=pv11pv22...pvss且至少有一个v大于1
把F(x)前的系数1也统一起来，定义莫比乌斯函数μ(d)=???1(-1)r0d = 1d=p1p2...pr,其中pi为不同的素数else原式写为f(x)=∑d∣xμ(xd)F(d)或f(x)=∑d∣xμ(d)F(xd)
构造性证明
如果已经构造好了莫比乌斯函数，证明只会更简单(T.T)
已知F(x)=∑d∣xf(d)，求证f(x)=∑d∣xμ(d)F(xd)
证明：∑d∣xμ(d)F(xd)=(1)∑d∣x[μ(d)∑k∣xdf(k)]=(2)∑k∣x[f(k)∑d∣xkμ(d)]=(3)f(x)
(1). xd作为整体，代入定义式
(2). 两边都为∑kd∣xf(k)μ(d)，左边提了μ(d)为公因子，右边提了f(k)为公因子，继续求和
(3). 令x=pv11pv22...pvss，给定k，则d为xk的约数。
当xk≠1，则d的取值为pa11pa22...pass(ai≤vi,ai不同时为0)，若有任何的ai&1则μ(d)=0，故只需考虑ai为0或1。ai组成的解向量(a1,a2,...,as)中有(...,0,...),(...,1,...)若省略的部分相同，这两者总是成对出现的，使得∑ai的奇偶性恰好相反，即有μ(d1)=1，就有μ(d2)=-1，两者和为0。得到当xk≠1,∑d∣xkμ(d)=0.
只有当xk=1,∑d∣xkμ(d)=1.
鸡冻ing…终于写完了….
莫比乌斯函数详解
在讲这个函数之前。最好先了解欧拉函数。
记为整除。 记得小学的时候整除和整除以的概念么？别混淆。 2整除4 记作 2\4。
欧拉函数用来表示。
那么根据法里级数的展开(这个感觉和A...
一种方便的证明莫比乌斯函数的方法
一种方便的证明莫比乌斯函数的方法一种方便的证明莫比乌斯函数的方法设有 f=g*1设有\ f = g * 1两侧都卷上μ, 得：μ*f=g*1*μ两侧都卷上\mu,\ 得：\mu * f = g * 1...
莫比乌斯反演定理证明（两种形式）
PoPoQQQ没有给出形式二的证明，我恨PoPoQQQ，证了好久。
证明之前，请先看看PoPoQQQ的ppt，当你看完发现没有证明想哭的时候，看看这篇博客。
F(n)=∑d|nf(d)...
莫比乌斯函数
在数论中的积性函数：对于正整数n的一个算术函数 f(n)，若f(1)=1，且当a,b互质时f(ab)=f(a)f(b)，在数论上就称它为积性函数。若对于某积性函数 f(n) ，就算a, b不互质，也有...
SPOJ-SQFREE SPOJ4168 莫比乌斯函数の性质
//题意：SPOJ-SQFREE，SPOJ内有多少个无平方因子数
//思路：莫比乌斯函数的性质。。实际上就是mu[i]^2的前缀和S
//然而直接搞会超时，S有Osqrtn的求法。公...
莫比乌斯函数学习笔记
e(n)=?1 n=10 n≠1e(n)=\lgroup^{1\ n=1}_{0\ n\neq1}
I(n)=1I(n)=1
id(n)=nid(n)=n
σ0(n)因子个数\...
BZOJ 2440 浅谈莫比乌斯函数性质推导
世界真的很大
莫比乌斯绝不是只有反演而已，其本身就是一个非常值得专研的函数
本质上来讲大概是指容斥时的系数规划，但也由此演化出了各种各样的有意思的东西
看题先：description小 X 自幼...
莫比乌斯函数和反演定理的理解
这几天复习了莫比乌斯函数的运用，主要是用来解决倍数的问题的。现在就谈谈莫比乌斯函数的性质和反演定理的理解。
首先定义 u(x)u(x) 为莫比乌斯函数。他有以下性质:
1.∑d|mu(x)=[m=...
莫比乌斯反演定理证明
首先证明一下定理一：
F(n)=∑d|nf(d)=&f(n)=∑d|nμ(nd)F(d)=∑d|nμ(d)f(nd)F(n)=\sum_{d|n}f(d) =&f(n)=\sum_{d|n}\mu(...
没有更多推荐了，}