莫比乌斯反演总结

莫比乌斯反演

Tags：数学

引用

YYB：http://www.cnblogs.com/cjyyb/p/7953803.html
YL：http://www.cnblogs.com/cjoieryl/p/8250019.html
ZSY：http://www.cnblogs.com/zhoushuyu/p/8186224.html

一、基本内容

《组合数学》P142写了详细内容，这里简单提一下：

Step1 Mobius函数

定义：

[mu(d)=egin{cases} 1quad quad quad d=1\ {(-1)}^r quad d=p1p2p3...pr\ 0quad quad quad 其他end{cases} ]

定理：

对于任意正整数n，恒有$$sum_{d|n}mu(d)=egin{cases} 1 quad n=1 0 quad n>1 end{cases}$$

证明：

(n)为(1)的时候很好证明，(n>1)的如下
首先(n)转化为(n')，(n={p1}^{a1}{p2}^{a2}...{pk}^{ak}),(n'=p1p2...pk)。
那么对于(d)有(n|d)那么(mu(d))无贡献，推出(mu(n)=mu(n'))
在(k)个质数中选(0)个（偶数个系数是(1)，由定义得）(+C(k,0))，选(1)个（奇数个系数是(-1)）(-C(k,1))，最后的式子就是（组合数公式）

[C(k,0)-C(k,1)+C(k,2)-...pm C(k,k)=0 ]

Step2 Mobius反演

形式A：

[g(x)=sum_{d|x}f(d) ]

[f(x)=sum_{d|x}mu(frac{x}{d})g(d) ]

形式B：

[g(x)=sum_{x|d}^{n}f(d) ]

[f(x)=sum_{x|d}^{n}mu(frac{d}{x})g(d) ]

这里给出形式(A)的证明

证明：

[f(x)=sum_{d|x}mu(frac{x}{d})sum_{d'|d}f(d') ]

对于每一个(f(d'))，如果说它要被计算到，那么一定存在一个(d)使得(d|x)且(d'|d)
那么就是(frac{x}{d'}|frac{x}{d})，被计算的次数是(mu(frac{x}{d}))

[f(x)=sum_{d'|x}f(d')sum_{frac{x}{d'}|frac{x}{d}}mu(frac{x}{d}) ]

然后由上面的定理得出当且仅当(frac{x}{d})为(1)时(mu(frac{x}{d}))不为(0)，为(1)，进而

[x=d,f(x)=sum_{d'|1}f(d')=f(x) ]

形式(B)同理可证，核心思想是把贡献提出来

Step 3 举个例子

求:$$sum_{i=1}^{N}sum_{j=1}{M}[gcd(i,j)==1]$$

Way 1

令$$f(x)=sum_{i=1}^{N}sum_{j=1}{M}[gcd(i,j)==x]$$

[g(x)=sum_{x|d}^{min(N,M)}f(d) ]

那么（中括号内表示成立为(1)否则为(0)）$$g(x)=sum_{x|d}^{{min(N,M)}sum_{i=1}}{N}sum_{j=1}^{{M}[gcd(i,j)==d]$$$$=sum_{i=1}}{N}sum_{j=1}^{M}[x|gcd(i,j)]=lfloorfrac{N}{x} floorlfloorfrac{M}{x} floor$$
进而$$f(x)=sum_{x|d}^{{min(N,M)}mu({frac{d}{x}})g(d)$$$$f(1)=sum_{i=1}}{min(N,M)}mu(i)lfloorfrac{N}{i} floorlfloorfrac{M}{i} floor$$
加上数论分块可以(O(sqrt{N}))完成（数论分块例题）

Way 2

由上面的莫比乌斯函数的定理可以知道$$[gcd(i,j)==1]=sum_{d|gcd(i,j)}mu(d)=sum_{d|i,d|j}mu(d)$$
所以说$$Ans=sum_{i=1}^{N}sum_{j=1}{M}sum_{d|i,d|j}mu(d)$$
提贡献：把(d)提到前面来$$Ans=sum_{d=1}^{{min(N,M)}mu(d)sum_{d|i}}{N}sum_{d|j}^{{M}1$$即$$Ans=sum_{d=1}}{min(N,M)}mu(d)lfloorfrac{N}{d} floorlfloorfrac{M}{d} floor$$

二、题目

三、做题经验

1、Mobius求解以下问题

(A、)[POI2007]ZAP-Queries（题解戳我）
　　(O(sqrt{n}))求下式（预处理(O(n))，还有拓展到(n)个(sigma)的Visible Lattice Points）

[sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)==k] ]

(B、)Gcd之和（题解戳我）
　　(O(n))求下式（jzptab要求单次询问(O(sqrt{n}))，题解戳我）

[sum_{i=1}^{n}sum_{j=1}^{m}gcd(i,j) ]

(C、)Crash的数字表格->单次(O(n))求下式
　　jzptab->单次(O(sqrt{n}))求下式（题解戳我）

[sum_{i=1}^{n}sum_{j=1}^{m}lcm(i,j) ]

(D、)Mophues（题解戳我/题解戳我）
　　(O(nsqrt{n}))预处理并单次(O(sqrt{n}))求下式，(Fact(i))表示(i)唯一分解后不同质因子的个数

[sum_{i=1}^{n}sum_{j=1}^{m}[Fact(gcd(i,j))<=P] ]

(E、)Code（题解戳我）
　　构造函数单次(O(nsqrt{n}))求下式，(A)为给定的一个数列，(A[i]<=1w)

[sum_{i=1}^{n}sum_{j=1}^{n}gcd(A[i],A[j])*(gcd(A[i],A[j])-1) ]

(F、)约数个数和（题解戳我【自己写的】）
　　(O(n))预处理并单次询问(O(sqrt{n}))处理下式，(d(i))为(i)的约数个数详见引理(B)$$sum_{i=1}^{n}sum_{j=1}{m}d(ij)$$

(G、)YY的GCD（题解戳我）
　　(O(n))预处理并单次询问(O(sqrt{n}))处理下式$$sum_{i=1}^{n}sum_{j=1}{m}[gcd(i,j)为质数?1:0]$$
(H、)Hillan and the girl（题解戳我）
　　(O(n))或(O(nloglogn))预处理并单次询问(O(sqrt{n}))$$sum_{i=1}^{n}sum_{j=1}{m}[gcd(i,j)为完全平方数?1:0]$$

(I、)于神之怒加强版（题解戳我）
　　(O(n))预处理并单次询问(O(sqrt{n}))$$sum_{i=1}^{n}sum_{j=1}{m}gcd(i,j)^k$$

(J、)数字表格（题解戳我）
　　(O(nloglogn))预处理并且单次询问(O(sqrt{n}))，其中(Feb(i))表示斐波那契数列第i项，(Feb(0)=0,Feb(1)=1...)$$prod_{i=1}^{{n}prod_{j=1}}{m}Feb(gcd(i,j))$$

2、小套路

(A、mu)只会用到(min(N,M))所以筛的时候可以不用筛到(MAXN)(助力冲榜)
(B、)数论分块套路（当数论分块会比较麻烦的时候可以用(Map)）

数论分块(lfloor{frac{n}{i}} floor)：([l,r])的值一定，则$$r=lfloor{frac{n}{lfloorfrac{n}{l} floor}} floor即r=n/(n/l)$$
数论分块(lfloor{frac{n}{i^2}} floor)：([l,r])的值一定，则$$r=lfloor{sqrt{lfloorfrac{n}{lfloorfrac{n}{l^2} floor}} floor} floor即r=sqrt(n/(n/l/l))$$
数论分块(lfloorsqrt{lfloor{frac{n}{i}} floor} floor)：([l,r])的值一定则$$r=lfloor{frac{n}{(lfloorsqrt{lfloorfrac{n}{l} floor} floor)^2}} floor即r=n/(sqrt(n/l)*sqrt(n/l))$$
总结

用(n)和(l)表示(x)，然后尝试用(n)和(x)把(l)表示回去，就得到了(r)
(Sample1)    (x=lfloorfrac{n}{l} floor)，(l=lfloorfrac{n}{x} floor)，(r=lfloor{frac{n}{lfloorfrac{n}{l} floor}} floor)
(Sample2)    (x=lfloorfrac{n}{l^2} floor)，(l=lfloorsqrt{lfloorfrac{n}{x} floor} floor)，(r=lfloor{sqrt{lfloorfrac{n}{lfloorfrac{n}{l^2} floor}} floor} floor)
(Sample3)    (x=lfloorsqrt{lfloorfrac{n}{l} floor} floor)，(l=lfloorfrac{n}{x^2} floor)，(r=lfloor{frac{n}{(lfloorsqrt{lfloorfrac{n}{l} floor} floor)^2}} floor)

(C、)提(gcd)套路（把(gcd)换成字母(d)，从枚举(i，j)改成枚举(d)）
(D、)提贡献套路(换元思想)：
　　令(T=id)然后把里面的(sigma)提取到外面，统计贡献
(E、)构造函数套路(Code)，不过不常用也很难想
(F、)线性筛积性函数，详见另一篇笔记《积性函数与线性筛》

3、注意事项

(A、)数据范围大的时候注意随时取模！！
(B、)有时候卡空间/时间，那么能用(int)尽量(int)，随时(1LL)

４、引理

(A、)$$lfloor{frac{frac{n}{i}}{d}} floor=lfloor{frac{n}{id}} floor$$　　令(n=a*(id)+b)，(b < id)
　　那么(lfloorfrac{n}{i} floor=a*d+lfloorfrac{b}{i} floor,lfloorfrac{b}{i} floor< d)
　　(lfloor{frac{frac{n}{i}}{d}} floor=a=lfloor{frac{n}{id}} floor)
　　
(B、)$$d(nm)=sum_{i|n}sum_{j|m}[gcd(i,j)==1]$$
　　(d(x))表示(x)的约数个数，如(d(6)=4)
　　任意(nm)的约数可以表示为(i*frac{m}{j})
　　如果(gcd(i,j)!=1)，可以令(i=k_1p,j=k_2p)，(i*frac{m}{j})表示的约数是(frac{k_1}{k_2m})，但是我们可以发现当(i=k_1,j=k_2)的时候就已经统计过这个约数了，再不懂可以手玩(4*6)
　　（Upd2018.8.15：公式写错了已更正 @Tyher）

有关原创文章

《线性筛》
《<约数个数和>题解》
《<安师大sanrd>题解》

Code

筛(mu(x))

void Mobius()
{
    mu[1]=1;ispri[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!ispri[i]) {pri[++tot]=i;mu[i]=-1;}
        for(int j=1;j<=tot&&i*pri[j]<=n;j++)
        {
            ispri[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    for(int i=1;i<=n;i++)s[i]=s[i-1]+mu[i];
}