莫比乌斯反演 (Möbius Inversion)

• 2018-08-30
• 0
• 0

[ 莫比乌斯反演公式 ]

设 $f(n)$, $g(n)$ 为定义于正整数域上的两个函数，并满足:

$$f(n)=\sum_{d|n}g(d)$$

则有以下反演公式:

$$g(n)=\sum_{d|n}f(\frac{n}{d})\mu(d)$$

[ 莫比乌斯函数 $\mu(i)$ ]

$$\mu(i)=\left\{\begin{array}{lcl}1\quad\quad\quad ,i=1 \\ (-1)^k\quad ,i=p_1*p_2*...*p_k \\ 0\quad\quad\quad ,otherwise\end{array}\right.\quad ,i\in N^*$$

[ 莫比乌斯反演相关推论 ]

1. $\mu(i)$ 为积性函数。
2. 若数论和函数 $F(n)=\sum_{d|n}f(n)$ 为积性函数，则 $f(n)$ 为积性函数。

3. $$\sum_{d|n}\mu(d)=[n=1]=\left\{\begin{array}{lcl}1,\quad n=1 \\ 0,\quad n>1\end{array}\right.$$

4. $$\sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}$$

[ 莫比乌斯反演证明 ]

由推论 3 得:

$$\sum_{d|n}\mu(d)=[n=1]\quad\quad\quad (1)$$

显然又有:

$$g(n)=\sum_{d|n}[\frac{n}{d}=1]g(d)\quad\quad\quad (2)$$

将 $(1)$ 代入 $(2)$ 得:

$$g(n)=\sum_{d|n}\sum_{c|\frac{n}{d}}\mu(c)g(d)$$

由于 $d|n$ 和 $c|\frac{n}{d}$ 的限制条件等价于 $cd|n$，可得:

$$g(n)=\sum_{c|n}\mu(c)\sum_{d|\frac{n}{c}}f(d)=\sum_{c|n}\mu(c)f(\frac{n}{c})$$

[ 莫比乌斯反演应用 ]

BZOJ 2301: https://www.lydsy.com/JudgeOnline/problem.php?id=2301

给出 $n$ 组询问 $a$, $b$, $c$, $d$, $k$，求 $\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]$。$1\leq n$, $a$, $b$, $c$, $d\leq 50000$。

考虑计算出二维前缀和 $S(n,m)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]$，则

$$S(n,m)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$

答案即为 $Ans=S(b,d)-S(a-1,d)-S(b,c-1)+S(a-1,c-1)$。

当 $1\leq i\leq\lfloor\frac{n}{k}\rfloor$, $1\leq j\leq\lfloor\frac{m}{k}\rfloor$ 时，令 $f(d)$ 表示 $gcd(i,j)=d$ 时 $(i,j)$ 的对数，$F(d)$ 表示 $d|gcd(i,j)$ 时 $(i,j)$ 的对数，则

$$F(d)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|gcd(i,j)]=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|i\land d|j]=\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$$

$$F(d)=\sum_{d|i}f(i)$$

根据莫比乌斯反演公式，上式可化为

$$f(d)=\sum_{d|i}F(i)\mu(\frac{i}{d})=\sum_{d|i}\mu(\frac{i}{d})\lfloor\frac{n}{ki}\rfloor\lfloor\frac{m}{ki}\rfloor$$

取 $d=1$，有

$$S(n,m)=f(1)=\sum_{i=1}^{min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(i)\lfloor\frac{n}{ki}\rfloor\lfloor\frac{m}{ki}\rfloor$$

考虑计算 $\sum_{i=1}^{min(n,m)}\mu(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$。

首先对 $\lfloor\frac{n}{i}\rfloor$ 的取值进行讨论:

1. 当 $1\leq i\leq\lfloor\sqrt{n}\rfloor$ 时，显然 $\lfloor\frac{n}{i}\rfloor$ 最多有 $\lfloor\sqrt{n}\rfloor$ 种不同取值。
2. 当 $\lfloor\sqrt{n}\rfloor <i\leq n$ 时，由于 $\lfloor\frac{n}{i}\rfloor\leq\lfloor\sqrt{n}\rfloor$，最多也有 $\lfloor\sqrt{n}\rfloor$ 种不同取值。

综上，$\lfloor\frac{n}{i}\rfloor$ 最多有 $2\lfloor\sqrt{n}\rfloor$ 种不同取值，且相同取值一定连续。

当循环到 $i$ 时，我们需要计算以 $i$ 开始，$\lfloor\frac{n}{i}\rfloor$ 和 $\lfloor\frac{m}{i}\rfloor$ 均不变的最大结束位置 $j$:

1. 计算以 $i$ 开始，$\lfloor\frac{n}{i}\rfloor$ 不变的最大位置 $j_1$。由于 $j_1$ 必定是满足 $\lfloor\frac{n}{j_1}\rfloor\geq\lfloor\frac{n}{i}\rfloor$ 的最大值， $j_1=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$。
2. 计算以 $i$ 开始，$\lfloor\frac{m}{i}\rfloor$ 不变的最大位置 $j_2$。同理 $j_2=\lfloor\frac{m}{\lfloor\frac{m}{i}\rfloor}\rfloor$。
3. $j=min(j_1,j_2)$。

根据上述分析，单次询问复杂度为 $O(\sqrt{n}+\sqrt{m})$，可以通过此题。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

inline void getint(int &num){
    register int ch, neg = 0;
    while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
    num = ch & 15;
    while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
    if(neg) num = -num;
}

int T, A, B, C, D, K;
int mu[50005], M[50005], prm[6005], pcnt = 0;
bool notprm[50005];

inline void Euler_Sieve(int n){
    notprm[1] = 1, mu[1] = 1;
    for(register int i = 2; i <= n; i++){
        if(!notprm[i]) prm[++pcnt] = i, mu[i] = -1;
        for(register int j = 1; j <= pcnt && i * prm[j] <= n; j++){
            notprm[i * prm[j]] = 1;
            if(i % prm[j] == 0) {mu[i * prm[j]] = 0; break;}
            mu[i * prm[j]] = -mu[i];
        }
    }
}

inline ll calc(int n, int m){
    ll res = 0; if(n > m) swap(n, m);
    for(register int i = 1, pos = 0; i <= n; i = pos + 1){
        pos = min(n / (n / i), m / (m / i));
        res += ll(M[pos] - M[i - 1]) * (n / i) * (m / i);
    }
    return res;
}

int main(){
    Euler_Sieve(50000);
    for(register int i = 1; i <= 50000; i++) M[i] = M[i - 1] + mu[i];
    getint(T);
    while(T--){
        getint(A), getint(B), getint(C), getint(D), getint(K);
        A = (A - 1) / K, B /= K, C = (C - 1) / K, D /= K;
        printf("%lld\n", calc(B, D) - calc(A, D) - calc(B, C) + calc(A, C));
    }
    return 0;
}