莫比乌斯反演 (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|nc|\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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai