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

  • 2018-08-30
  • 0
  • 2

[ 莫比乌斯反演公式 ]

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;
}

评论

  • Vickie回复

    I do consider all the ideas you've offered for your post.
    They are very convincing and will definitely work. Nonetheless, the posts are very quick for novices.

    May just you please extend them a little from subsequent time?

    Thanks for the post.



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

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


OPEN AT 2017.12.10

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


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
















- Theme by Qzhai