zcmimi's blog
avatar
zcmimi
2020-03-12 20:40:00

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

\mu (i)= \begin{cases} 1,i=1 \\ (-1)^k,i=p_1\times p_2\times \dots \times p_k \\ 0,rest \end{cases}

性质

以下证明可以先了解狄利克雷卷积

并强烈推荐了解: https://www.luogu.com.cn/blog/lx-2003/mobius-inversion

  1. \sum_{d|n}\mu(d)=[n=1] \\\Downarrow\\ [gcd(a,b)=1]=\sum_{d|\gcd(a,b)}\mu(d)

  2. \sum_{d|n}\frac{\mu(d)}d = \frac{\varphi(n)}n

  3. \mu是积性函数,若\gcd(a,b)=1,\mu(ab)=\mu(a)\cdot\mu(b)

  4. 反演: g(x)=\sum_{x|d}f(d) \\\Updownarrow\\ f(x)=\sum_{x|d}\mu(\frac dx) \cdot g(d)

线性筛莫比乌斯函数

int mu[N],pri[N],cnt=0;
bool f[N];
il void getmu(int n){
    mu[1]=1;
    Fur(i,2,n){
        if(!f[i])mu[i]=-1,pri[++cnt]=i;
        Fur(j,1,cnt){
            if(pri[j]*i>n)break;
            f[i*pri[j]]=1;
            if(i%pri[j])mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
}

实例

(默认n<m)

Eg1

求:

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

解:

\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=1] \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i,j)} \mu(d) \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{d|i,d|j} \mu(d) \\ =\sum_{d=1}^n\mu(d)\left \lfloor \frac nd \right \rfloor \left \lfloor \frac md\right \rfloor

将复杂度成功降到了O(\sqrt n)

Eg2

求:

\sum_{i=1}^n\sum_{i=1}^mgcd(i,j)

解:

\sum_{i=1}^n\sum_{j=1}^mgcd(i,j) \\ =\sum_{d=1}^n d\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d] \\ =\sum_{d=1}^n d\sum_{i=1}^{\left\lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left\lfloor \frac md \right \rfloor}[gcd(i,j)=1]

利用Eg1的结果

=\sum_{d=1}^n d\sum_{i=1}^{\left\lfloor \frac nd \right \rfloor}\mu(i)\left \lfloor \frac n{id} \right \rfloor \left \lfloor \frac m{id}\right \rfloor

这时候分块套分块复杂度可能还是会tle,我们可以继续优化

T=id

=\sum_{T=1}^n \left \lfloor \frac nT \right \rfloor \left \lfloor \frac mT\right \rfloor \sum_{d|T} d\mu(\frac Td)

成功降到了O(\sqrt n)

Eg3

求:

\sum_{i=1}^n\sum_{j=1}^m f(\gcd(i,j))

解:

\sum_{i=1}^n\sum_{j=1}^m f(\gcd(i,j)) \\ =\sum_{d=1}^n f(d) \sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d] \\ =\sum_{d=1}^n f(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} [\gcd(i,j)=1] \\ =\sum_{d=1}^n f(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n f(d) \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor} \mu(x) {\left \lfloor \frac n{dx} \right \rfloor}{\left \lfloor \frac m{dx} \right \rfloor}

T=dx

=\sum_{T=1}^n {\left \lfloor \frac nT \right \rfloor}{\left \lfloor \frac mT \right \rfloor}\sum_{d|T}f(d) \mu(\left \lfloor \frac Td \right \rfloor)

求出或维护函数s(T)=\sum_{d|T}f(d) \mu(\left \lfloor \frac Td \right \rfloor)的前缀和,

然后就可以数论分块O(\sqrt n)求解了

https://www.luogu.com.cn/problem/P3312

Eg4

求:

\prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)}

解:

\prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=d]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

求出或维护函数s(T)=\sum_{d|T}f(d) \mu(\left \lfloor \frac Td \right \rfloor)的前缀积,

然后就可以数论分块O(\sqrt n)求解了

https://www.luogu.com.cn/problem/P3704

莫比乌斯函数
comment评论
Search
search