数论 莫比乌斯函数 莫比乌斯反演

1.1 莫比乌斯函数的性质

一、 莫比乌斯函数具有积性

证明也比较好想：莫比乌斯函数具有的是积性，而非完全积性，因此两数必定互质。对于(mu(a)times mu(b)),倘若a含平方因数(b同理)，则(mu(a)=0),结果也为(0)；若a,b都不含平方因数，又因为a,b互质， 因此a,b的贡献为提供不同数目的质因数，可以累加。

二、 结论：(forall n quad sum_{d|n} mu(d)=lfloor frac{1}{n}rfloor)

证明：

n=1时，结论显然

设(n=p_1^{a_1}+..+p_k^{a_k}),含有平方因子的(d)，其(mu(d)=0)，不会对答案产生影响，因此剩下需要被讨论的(d)一定可以被(p_1 .. p_k)之间的乘积表示出来。

由二项定理可知：(sum_{i=0}^n C_n^itimes x^itimes y^{n-i})

将(x=1,y=-1)代入可得
(sum_{i=0}^n C_n^itimes(-1)^i=0)

至此，结论得到证明

三、 (mu * I = epsilon)

其实展开后会发现与性质二无异

1.2 莫比乌斯函数的线性筛法

莫比乌斯函数的线性筛法套用了欧拉线性筛的框架，将求解分成了三部分

设当前求解的数是 (x)

1. 若 (x = prime) ，则(mu(x)=-1)

这一点可以根据定义简单证明

2. 若(imod prime[j] = 0)，则(mu(itimes prime[j])=0)

根据定义，倘若存在平方因子，则函数值为 (0)

3. 若 (imod prime[j] not = 0)，则 (mu(itimes prime[j])=-mu(i))

因为(prime[j])不与(i)互质，因此(prime[j])的作用也便是多提供一个质因子，因此直接取反即可

先复习一遍欧拉筛：

namespace prime_sieve{
    const int MAX=1e6+5,TOP=1e6;
    bool vis[MAX]; int prime[MAX];

    void work(){
        vis[1]=true;
        lor(i,2,TOP){
            if(!vis[i]) prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&prime[j]*i<=TOP;++j){
                vis[prime[j]*i]=true;
                if(i%prime[j]==0) break;
            }
        }
    }
}

理解欧拉筛之后，把它改造成莫比乌斯筛：

namespace mobius_sieve{
    const int MAX=1e6+5,TOP=1e6;
    bool vis[MAX]; int prime[MAX],mob[MAX];

    void work(){
        vis[1]=true; mob[1]=1;
        lor(i,2,TOP){
            if(!vis[i]) {prime[++prime[0]]=i; mob[i]=-1;} \ 情况一
            for(int j=1;j<=prime[0]&&i*prime[j]<=TOP;++j){
                vis[i*prime[j]]=true;
                if(i%prime[j]==0) {mob[i*prime[j]]=0; break;} \ 情况二
                else mob[i*prime[j]]=-mob[i]; \ 情况三
            }
        }
    }
}

只是在筛素数的同时串插了莫比乌斯函数的求解，应该比较好理解(～￣▽￣)～

2.1 莫比乌斯反演——形式一 （约数形式）

还是先陈述一遍结论:

2.1.1 卷积法证明

2.1.2 定义法证明

为了防止以后回想不起来，记录一下当时推导过程中的小障碍：

1） 第三行与第四行： (d)和(k)互相可以调换，因为彼此间没有特殊性

2） 第六行：中括号为艾佛森括号，返回一个布尔值。而之所以可以从第五行转移过来是根据莫比乌斯性质二：(forall quad x sum_{d|x}mu[d]=[x=1])

2.2 莫比乌斯反演——形式二 （倍数形式）

2.2.1 卷积法证明

这..和卷积的定义都不一样，可能无法证明？(っ °Д °;)っ

等以后学会了再填坑吧

2.2.2 定义法证明

1. 第二行到第三行： 从f[]的视角总结f[]被累乘情况

3.1 例题一

四元组统计

设(f[i])表示四元组gcd=i的方案数。显然(f[1])就是答案，但是求解非常困难。

那么就考虑转移，另设(g[i])表示四元组gcd=i的倍数的方案数。一个显然的等式是：

根据莫比乌斯反演可得：

而(g[])的求解就要比(f[])友善得多。统计出(num)的倍数在原数组中出现的次数后，(f[num]=C_{cnt}^4)

此外，一个小坑在于：直接去计数将会导致TLE，需要采取累似桶排的思想，枚举(i=num)，然后每次转移(i+=num)，取累加(buc[i])。可以有效提速φ(゜▽゜*)♪