莫比乌斯反演

 

莫比乌斯反演这东西其实能解决的问题非常多。

首先看莫比乌斯反演的前置知识：莫比乌斯函数。

莫比乌斯函数

定义 Mobius 函数 为：

$$\mu (x) = \left\{ \begin{aligned} &1 &(x = 1)\\ &(-1)^n &(x = p_1 p_2 p_3 \cdots p_n，其中 p_i 为质数) \\ &0 &(其它情况，即为存在一个质数的平方项) \end{aligned} \right.$$

Mobius 函数是一个积性函数（即为对于任意互质的整数 ，），于是可以在 的复杂度内，利用线性筛来求得 的所有的 Mobius 函数。

int prime[N], primecnt;
int mobius[N], summob[N];
bool vis[N];
void init(){
    vis[1] = mobius[1] = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            mobius[i] = -1;
            prime[++primecnt] = i;
        }
        for(int j=1;j<=primecnt && prime[j]*i<=n; j++){
            vis[prime[j]*i] =1;
            mobius[prime[j]*i] = (i%prime[j]?-mobius[i]: 0);
            if(i%prime[j] == 0) break;
        }
    }
}

而 Mobius 函数有一个重要的性质：

$$\displaystyle\sum_{d\mid n}\mu(d) = [n = 1]$$

这个是莫比乌斯函数的最重要的性质！一定要把它狠狠地记住，几乎所有的莫反的题都用到了这个性质。

接下来可以讲一道例题来理解这个性质：

P1390 公约数的和

题目描述：

给定 ，求

$$\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)$$

其中 表示 和 的最大公约数，。

---

首先，我们把 转化为 。

我们可以推导这个式子：

$$\begin{aligned} & \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) \\ = &\sum_{i = 1}^n \sum_{j = 1}^n \sum_{d=1}^{n} [\gcd(i, j) = d]\cdot d \\ = &\sum_{d=1}^{n}d\cdot \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \\ = &\sum_{d=1}^{n} d \cdot \sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j = 1}^{\lfloor{\frac{n}{d}}\rfloor} [\gcd(i, j) = 1] \end{aligned}$$

然后根据上面的性质，。

我们先把后面的 提出来，令其为 。并且令 为 。

于是乎：

$$\begin{aligned} y &= \sum_{i = 1}^p \sum_{j = 1}^p [\gcd(i, j) = 1]\\ &= \sum_{i = 1}^p \sum_{j = 1}^p \sum_{k\mid \gcd(i,j)} \mu(k)\\ &= \sum_{i = 1}^p \sum_{j = 1}^p \sum_{k\mid i \land k \mid j} \mu(k) \\ &= \sum_{k=1}^{p} \mu(k)\cdot\sum_{i=1}^{\lfloor\frac{p}{k}\rfloor}\sum_{j=1}^{\lfloor{\frac{p}{k}\rfloor}} 1\\ &= \sum_{k=1}^{p} \mu(k) \cdot (\lfloor{\frac{p}{k}}\rfloor)^2 \end{aligned}$$

于是我们惊喜地发现：这个式子 其实可以用数论分块做！ 就可以用之前提到的线性筛 求 Mobius 函数，再给其做前缀和处理。于是我们把复杂度降到了 ，此复杂度足以通过此题也。

其实足够细心的话，你可以发现，，这也是一个数论分块。于是复杂度就又可以被压到 了。这个数论分块就是对这道题的一个显著的优化。

版本：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+6;
bool vis[N];
int mobius[N], summob[N];
int prime[N];
int n, primecnt;
void init(){
    mobius[1] = 1;
    vis[1] = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) vis[i] = 1, prime[++primecnt] = i, mobius[i] = -1;
        for(int j=1;j<=primecnt && prime[j] * i <= n; j++){
            vis[prime[j] * i] = 1;
            mobius[prime[j] * i] = (i % prime[j] ? -mobius[i]: 0);
            if(i % prime[j] == 0) break;
        }
    }
    for(int i=1;i<=n;i++)
        summob[i] = summob[i-1] + mobius[i];
}

ll solve(int lim){
    int l = 0, r = 0;
    ll ans = 0;
    while(r < lim){
        l = r + 1;
        r = lim/(lim/l);
        ans += 1ll*(lim/l)*(lim/l)*(summob[r]-summob[l-1]);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    init();
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ans += i * solve(n/i);
    }
    ans -= 1ll*(n+1)*n/2;
    ans /= 2;
    cout<<ans;
    return 0;
}

版本（只需更改主函数即可）：

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n;
    init();
    ll ans = 0;
    int l = 0, r = 0;
    while(r < n){
        l = r+1;
        r = n/(n/l);
        ans += 1ll * (l+r)*(r-l+1)/2 * solve(n/l);
    }
    ans -= 1ll*(n+1)*n/2;
    ans /= 2;
    cout<<ans<<'\n';
    return 0;
}

其变种：

题目描述：

给定 ，求

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

其中 表示 和 的最大公约数，。多测， 组数据，。

---

一样，先将其推到

$$\sum_{k=1}^{\lfloor\frac{\min(n, m)}{d}\rfloor} \mu(k) \cdot (\lfloor{\frac{n}{dk}}\rfloor)(\lfloor \frac{m}{dk}\rfloor)$$

然后利用整除分块做。不过，这里的整除分块要稍微做个小改动，一段区间是 ：

long long solve(int x, int y){
    if(x<y) swap(x, y);
    int l = 0, r = 0;
    long long ans = 0;
    while(r < y){
        l = r + 1;
        r = min(x/(x/l), y/(y/l));
        ans += 1ll * (summob[r] - summob[l-1]) * (x/l) * (y/l);
    }
    return ans;
}

于是这道题就做完了。

注意上面的第二行！一定要先确保是大的数在前面还是小的数在前面，你不知道出题人什么时候会给你搞一些幺蛾子出来。

续集：欧拉反演和杜教筛

P1447 能量采集

这道题首先看到这个图，就会想起来有一道类似的题目，可以作为一道双倍经验。

我们要求原点 和目标点 点中间有没有点会挡住这两个点的连线。

不是那么得显然的、当 时，中间没有玩意挡住连线。如果有的话，挡住连线的植物的个数就是 个。

考虑如何证明。我们令 。因为斜率相同，那么首先就会有 给他挡住，然后 又给他挡住，然后是 ……最后就是 ，即 了。

于是，对于每个点的能量损失 ，我们就给他转化为了 。

于是就可以套上莫反板子，开做！

P2231 跳蚤

这道题就是让我们求，给定序列 的范围 ，使方程

$$a_1x_1 + a_2x_2 + \cdots + a_nx_n + mx_{n+1} = 1$$

有整数解的 序列的可能的不同的取值个数。

根据裴蜀定理的多个整数的推广：

设 为不全为 的整数，则存在整数 ，使得 。

（节选自 OI-Wiki）

于是我们可以推断：。

即让我们求：

$$\sum_{a_1 = 0}^{m} \sum_{a_2 = 0}^{m} \cdots \sum_{a_n=0}^{m} [\gcd(a_1, a_2, \cdots, a_n, m) = 1]$$

因为序列中只要有一个 ，这个序列的公因数就为 。即可以转为：

$$\sum_{a_1 = 1}^{m} \sum_{a_2 = 1}^{m} \cdots \sum_{a_n=1}^{m} [\gcd(a_1, a_2, \cdots, a_n, m) = 1]$$

根据莫比乌斯函数性质，则将其转为：

$$\sum_{a_1 = 1}^{m} \sum_{a_2 = 1}^{m} \cdots \sum_{a_n=1}^{m}\sum_{d \mid gcd(a_1, a_2, \cdots a_n, m)} \mu(d) \\ = \sum_{a_1 = 1}^{m} \sum_{a_2 = 1}^{m} \cdots \sum_{a_n=1}^{m}\sum_{d \mid a_1 \land d\mid a_2 \land \cdots \land d \mid a_n \land d \mid m} \mu(d)$$

即：

$$\sum_{d \mid m} \mu(d)\cdot\sum_{a_1 = 1}^{\lfloor\frac{m}{d}\rfloor} \sum_{a_2 = 1}^{\lfloor\frac{m}{d}\rfloor} \cdots \sum_{a_n = 1}^{\lfloor\frac{m}{d}\rfloor} 1 \\ = \sum_{d \mid m} \mu(d) \cdot (\lfloor\frac{m}{d}\rfloor)^{n}$$

而因为当 为 或没有平方项的质数的乘积时， 才对答案有贡献（即值为 或 。没有贡献的值就是 ，因为它根本影响不了答案）。所以我们可以先将 质因数分解，然后枚举 包含了 的哪些质因子。 因为有枚举的质因数个数，所以可以现算。然后后面的那个 次方的玩意直接快速幂算出来即可。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m;
int prime[N], primecnt;
void divide(int x){
    int lim = sqrt(x);
    for(int i=2;i<=lim && i<=x;i++){
        if(x%i==0){
            prime[++primecnt] = i;
            while(x%i==0) x/=i;
        }
    }
    if(x!=1) prime[++primecnt] = x;
}
typedef long long ll;
ll ans = 0;
ll ksm(ll bas, ll x){
    ll ans = 1;
    while(x){
        if(x&1) ans = ans * bas;
        bas = bas * bas;
        x >>= 1;
    }
    return ans;
}
void dfs(int x, int mu, int m_d){
    // int d;
    ans += mu * ksm(m_d, n);
    for(int i=x;i<=primecnt;i++){
        dfs(i+1, mu*(-1), m_d / prime[i]);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    divide(m);
    dfs(1, 1, m);
    cout<<ans<<'\n';
}