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

在学习下面的内容之前，最好先掌握：唯一分解定理、、整除分块、

一、莫比乌斯函数

简介：莫比乌斯函数是一种数论函数，由德国数学家、天文学家莫比乌斯(Möbius ,1790–1868)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。莫比乌斯函数在数论中有着广泛应用。

（一）、入门

莫比乌斯函数完整定义的通俗表达：
1）莫比乌斯函数μ(n)的定义域是N*
2）μ(1) = 1
3）当n存在平方因子时，μ(n) = 0
4）当n是素数或奇数个不同素数之积时，μ(n) =  -1
5）当n是偶数个不同素数之积时，μ(n)=1

或者：

可以看出：质数的μ值为-1

 例如：
μ(8) = μ(2^3) = μ(2^2×2) = 0（n存在平方因子）
μ(12) = μ(2^2×3) = 0（n存在平方因子）
μ(18) = μ(2×3^2) = 0（n存在平方因子）
μ(2) = -1（n是素数）
μ(3) = -1（n是质数）
μ(30) =μ(2×3×5)= -1（n是奇数个不同素数之积）
μ(1)= 1，μ(6)=μ(2×3)，μ(10)=μ(2×5) = 1

（二）、性质

性质一：莫比乌斯函数是积性函数。

应用：根据这一性质，我们可以采取线性筛法，用 O(n) 的时间预处理出所有 [1, n] 内的莫比乌斯函数值。
质数的μ值为 -1，如果一个数存在某个质因子的指数不为 1，那么它将会被筛为 0（值得注意的是，只有数n存在最小质因子的指数大于 1 时，它才会被直接筛为 0，其余的情况是μ(d)=−μ(i) 来完成的）。
每个数仅被其最小质因子筛去，故复杂度为 O(n)。

#include<cstdio>
const int N = 1e6 + 5;
int mu[N], vis[N], prime[N];
int tot;//用来记录prime的个数
void init(){
    mu[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!vis[i]){
            prime[tot ++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j ++){
            vis[i * prime[j]] = 1;
            if(i % prime[j]) mu[i * prime[j]] = -mu[i];
            else{
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}
int main(){
    init();
}

性质二：

证明：

• n=1 时, μ(1)=1.

• n!=1 时,

• n的因子

• 由于 质因子幂 大于 1 的 μ 值为 0, 所以只需考虑幂为 0,1 的质因子项,

• 二项式定理:

例如：n=1时，d=1,μ(d)=μ(1)=1

n>1时，比如4，d=1,2,4 μ(1)+μ(2)+μ(4)=1-1+0=0

也可以写成

还可以这样用：把n换成gcd(i,j)或者换成其它的

看下面的经典应用一、二、三、四

性质三：

考虑求下面这个式子

先枚举了i，再考虑i所有的约数

等价于：先枚举d ，再考虑d所在范围内所有的倍数

所以上式等于：

时间复杂度减少了一维

性质四：

其中φ(n)是欧拉函数

 （三）、莫比乌斯函数的应用

1.经典应用一：（必须理解和掌握）

求

[gcd(i,j)=1]的意思是当gcd(i,j)等于1时[gcd(i,j)=1]=1，否则为[gcd(i,j)=1]=0

解：由性质二可知

对于第三个和式，条件为d|gcd(i,j)，即为枚举能整除gcd(i,j)的d并计算μ(d)的和，可以变成枚举能整除i的d，再枚举能整除j的d

注意到这个d是既能整除i又能整除j的数，那可以调换一下第二、三个和式的顺序

由性质三可知：

再套性质三：

注意到这两个d是一样的，那么只能取min(n,m)，运用乘法交换律：

为什么也是红色，实际上你可以把这个式子看作是莫比乌斯函数的第五条性质，做题的时间拿来用就是。

注意到后面那一坨是可以O(√n)分块做的

于是我们实现了O(n^2)到O(√n​)的过渡

另：还有求

m改成n，也是一样了 

两样也可以把它看作一个公式，直接套用。

练习题：

P1390公约数的和、UVa11417、SP3871 GCDEX - GCD Extreme、UVA11424 GCD - Extreme (I)、UVa11426 拿行李（极限版） GCD - Extreme (II)

2.经典应用二：（必须理解和掌握）

给定n,m，求：

其中[gcd(i,j)==x]表示当gcd(i,j)==x时返回1，否则返回0。

要求时间复杂度为O(n)

上面的有点啰嗦，其实还可以这么理解

同时除以x，得

然后就和经典应用一是一样的了

3.经典应用三：（必须理解和掌握）

求

-------------1式

老方法，同时除以k，只不过与上一题不同的是，我们需要考虑i,j的贡献

 ------------2式

有同学可能要问了

因为在i,j同时除以k的同时，中间那个i，j的值就变了，i，j同时缩小到了原来的1/k​，所以最后要把缩小的乘回来，就是k^2

举例：n=6,m=8,k=2，那么1式为下表

2式为下表：

从这个表中可以看出i和j都被缩小为原来的1/k了，所以要乘回来

让我们继续套路，将中间那个gcd(i,j)用莫比乌斯替换掉

如果忽视ij和k^2那么就是和经典应用一相同了

提出d，同样，在最后乘以一个d^2，理由同上面的k^2

各归各家，各找各妈

我们发现，最后那两项，不就是…等差数列吗？

时间复杂度O(n^2)→O(根号n​)

插一个有意思的问题，其中没用到莫比乌斯反演

问题是求

方法一：欧拉函数反演

前备知识

可推得：

则：

d∣gcd(i,j)显然又可以写成 d∣i and d∣j 即d∣i,j

这个东西还可以稍微扩展一下，把其中一个n换成m

方法二：莫比乌斯反演

这个下面再说

 二、莫比乌斯反演

什么是反演？可以暂时理解为一种神奇的、打破常规思维（高大上）的运算！

（一）、入门（推公式）

例如:根据F（n）函数定义可知下列表格一（以计算到F(8)为例）

利用表格一解方程，我们得到表格二：

观察发现，f(n)等于形式为，再结合前面的各个自然数的莫比乌斯函数值把上们的式子改一下成表格三：

所以我们推出一个公式：（特点是约数和，其中d是n的约数）

（想想右边两个式子为什么相等）

还有第二种形式的公式：（特点是倍数和，其中d是n的倍数）（这个公式用得多）

再次强调这个公式中的d是n的倍数，不是通常理解的约数！！！

（二）、定义

什么是莫比乌斯反演？

对于一些函数f(n)，如果我们很难直接求出它的值，而容易求出倍数和或约数和F(n)，那么我们可以通过莫比乌斯反演来求得f(n)的值。

实际上是一个定理

莫比乌斯反演定理: 

对于待求解函数f(n)

第一步：先构造另一个约数和（或倍数和）函数F(n)，它满足

       或者      

第二步：计算F（n）和莫比乌斯函数μ(n)

第三步：通过F(n)、莫比乌斯函数μ()来求解f(n)

      或者       

上述的过程就叫莫比乌斯反演（又叫莫比乌斯约数反演和倍数反演），上面的两个公式就叫莫比乌斯反演公式。

4、莫比乌斯反演的作用

对于上面所提到的f()函数，在求解时如果发现时间复杂度高达o(n^2)，而求解F（）函数时去只需要o(n)时间复杂度，则可以通过反演降低时间复杂度

（三）、莫比乌斯反演的应用

1、求解gcd(i,j)=1的对数

2、求解gcd(i,j)=k的对数

3、求解gcd(i,j)的幂

1.例1（在莫比乌斯函数中应用二中已经有一种解法）

比如说给定n,m，求：

其中[gcd(i,j)==x]表示当gcd(i,j)==x时返回1，否则返回0。

要求时间复杂度为O(n)

按照上面的公式，我们构造一个倍数和函数g(x)满足：

用倍数和反演一波：

仿佛并没有什么用的样子。。。，那先来看一下“所谓”好求的g(x)

可以发现gcd(i,j)是x的倍数时（因为d只能是x的倍数，所以gcd(i,j)也是x的倍数），才会对g(x)造成贡献，所以，g(x)可以简化为

我们设g=gcd(i,j)，i=g*a，j=g*b ，我们在改变a，b的值时gcd(i,j)也会改变但始终是x的倍数（因为i,j至少都有一个因子g），所以，我们只需要取完a，b的所有的值就可以求出g(x)啦

很明显a能取的值有种，b能取的值有种，所以g(x)=，这玩意大大地降低了时间复杂度

再把g(x)带进去

很明显可以O(n)做了 

关于莫比乌斯反演的几个技巧

1、分块优化（也叫数论分块、整除分块）

long long solve(int n,int m,int k)
{
    if(n>m) swap(n,m);
    if(!n||!m||!k) return 0;
    n/=k;m/=k;
    LL ans=0;
    int last,i;
    for(i=1;i<=n;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ans=1ll*ans+1ll*(n/i)*(m/i)*(mu[last]-mu[i-1]);
    }
    return ans;
}

例题：

2、数论中的应用二：

设f1(n)=n，f2(n)=1

那么根据反演公式有

很神奇，是吧。

3、应用三：

不知道你对欧拉函数那篇文章中的这个结论还有没有印象

3、n的因数（包括1和它自己）的欧拉函数之和等于n。记为

4、应用四：

题意：给一个正整数，其中，求使得为质数的的个数，。

分析：对于本题，因为是使得为质数，所以必然要枚举小于等于的质数，那么对于每一个质数，只

     需要求在区间中，满足有序对互质的对数。

     也就是说，现在问题转化为：在区间中，存在多少个有序对使得互质，这个问题就简单啦，因为

     是有序对，不妨设，那么我们如果枚举每一个，小于有多少个与互素，这正是欧拉函数。所以

     我们可以递推法求欧拉函数，将得到的答案乘以2即可，但是这里乘以2后还有漏计算了的，那么有哪些呢？

     是且为素数的情况，再加上就行了。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <bitset> 
using namespace std;
typedef long long LL;
const int N = 10000010; 
bitset<N> prime;
LL phi[N];
LL f[N];
int p[N];
int k; 
void isprime(){
    k = 0;
    prime.set();
    for(int i=2; i<N; i++){
        if(prime[i]){
            p[k++] = i;
            for(int j=i+i; j<N; j+=i)
                prime[j] = false;
        }
    }
} 
void Init(){
    for(int i=1; i<N; i++)  phi[i] = i;
    for(int i=2; i<N; i+=2) phi[i] >>= 1;
    for(int i=3; i<N; i+=2){
        if(phi[i] == i){
            for(int j=i; j<N; j+=i)
                phi[j] = phi[j] - phi[j] / i;
        }
    }
    f[1] = 0;
    for(int i=2;i<N;i++)
        f[i] = f[i-1] + (phi[i]<<1);
} 
LL Solve(int n){
    LL ans = 0;
    for(int i=0; i<k&&p[i]<=n; i++)
        ans += 1 + f[n/p[i]];
    return ans;
} 
int main(){
    Init();
    isprime();
    int n;
    scanf("%d",&n);
    printf("%I64d\n",Solve(n));
    return 0;
}

嗯，上题不算太难，普通的欧拉函数就可以搞定，接下来我们来看看它的升级版。

题意：给定两个数和，其中，，求为质数的有多少对？其中和的范

     围是。

分析：本题与上题不同的是和不一定相同。在这里我们用莫比乌斯反演来解决，文章开头也说了它能大大简化

     运算。我们知道莫比乌斯反演的一般描述为：

     其实它还有另一种描述，本题也是用到这种。那就是：

     好了，到了这里，我们开始进入正题。。。

     对于本题，我们设

     为满足且和的的对数

     为满足且和的的对数

     那么，很显然，反演后得到

     因为题目要求是为质数，那么我们枚举每一个质数，然后得到

     如果直接这样做肯定TLE，那么我们必须优化。

     我们设，那么继续得到。

     到了这里，可以看出如果我们可以先预处理出所有的对应的的值，那么本题就解决了。

     我们设，注意这里为素数，。

     那么，我们枚举每一个，得到，现在分情况讨论：

     （1）如果整除，那么得到

     （2）如果不整除，那么得到

#include <iostream>
#include <string.h>
#include <stdio.h>
 
using namespace std;
typedef long long LL;
const int N = 10000005;
 
bool vis[N];
int p[N];
int cnt;
int g[N],u[N],sum[N];
 
void Init(){
    memset(vis,0,sizeof(vis));
    u[1] = 1;
    cnt = 0;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            p[cnt++] = i;
            u[i] = -1;
            g[i] = 1;
        }
        for(int j=0;j<cnt&&i*p[j]<N;j++){
            vis[i*p[j]] = 1;
            if(i%p[j]){
                u[i*p[j]] = -u[i];
                g[i*p[j]] = u[i] - g[i];
            }else{
                u[i*p[j]] = 0;
                g[i*p[j]] = u[i];
                break;
            }
        }
    }
    sum[0] = 0;
    for(int i=1;i<N;i++)
        sum[i] = sum[i-1] + g[i];
}
 
int main(){
    Init();
    int T;
    scanf("%d",&T);
    while(T--){
        LL n,m;
        cin>>n>>m;
        if(n > m) swap(n,m);
        LL ans = 0;
        for(int i=1,last;i<=n;i=last+1){
            last = min(n/(n/i),m/(m/i));
            ans += (n/i)*(m/i)*(sum[last]-sum[i-1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}