莫比乌斯反演与积性函数

发表于 更新于 阅读次数：

莫比乌斯反演与求解积性函数相关问题是数论中十分重要的一环，这里记录一下莫反的一些思路和配套工具。

莫比乌斯反演

其实就下面这两个式子：

1.

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

\Updownarrow

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

证明：

\because(f*g)(n)=\sum_{d|n}f(d)g\left(\frac{n}{d}\right)

\therefore g(n)=\sum_{d|n}f(d)=f*I,(I(n)=1)

\text{两边都卷一个}\mu

\because\mu*I=\sum_{d|n}\mu(d)=[n=1]

\therefore g*\mu=f

\because\text{只有$\frac{n}{d}=1$即$d=n$的时候有值。}

\therefore f*[n=1]=f

\therefore g*\mu=f

\text{把这个狄利克雷卷积展开即可得到}

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

2.

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

\Updownarrow

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

  • （注意这个 d一般就是 f的定义域或者说是“函数值有效”的定义域）

式子 2还不晓得怎么证明(3.10)

填坑(3.15):

在昨天听教授的组合数学的时候突然想了一下公式2的证明，然后好像突然会证了？？？网上关于式子2的证明大多数都写的不明不白，亦或者是用积分证的让人没有读的欲望，所以在这里给一篇浅显易懂的证明：

证明：

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

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

我们设m为f函数的“上界”，就跟之前我们n|d时那个d的范围一样，可以当成正无穷理解。

那么我们更改枚举项，i表示d是n的几倍，j表示D是d的几倍。

那么:

\text{原式}=\sum_{i=1}^{\lfloor\frac{m}{n}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{in}\rfloor}f(ijn)\mu(i)

显然这个ij不好处理，那么我们再次更改枚举项：

\text{令}T=ij

\text{那么原式}=\sum_{T=1}^{\lfloor\frac{m}{n}\rfloor}\sum_{i|T}\mu(i)f(Tn)

大家看一下中间那个式子:

\sum_{i|T}\mu(i)=[n=1]

这个证明用二项式定理就可以证明：

\text{设T有n个质因子}

\sum_{i|T}\mu(i)=\sum_{i=0}^{n}\tbinom{n}{i}(-1)^i=(1-1)^n

  • 只有n=0即T=1的时候原式才为1，否则为0

  • 这也是为什么证明1中\mu*I=[n=1]

至于二项式定理可以用组合意义自己手玩一下，再在这里证就扯远了。

\text{综上:}

\sum_{T=1}^{\lfloor\frac{m}{n}\rfloor}\sum_{i|T}\mu(i)f(Tn)=f(n)=\sum_{n|d}g(d)\mu\left(\frac{d}{n}\right)

莫比乌斯反演常见套路：

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

令

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

那么有

g(x)=\sum_{x|d}f(d)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]

\because[x|gcd(i,j)]

\therefore x|i\text{且}x|j

然后直接枚举 i，j是 x的多少倍

g(x)=\sum_{i=1}^n\sum_{j=1}^m[x|gcd(i,j)]=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}=\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor

然后莫比乌斯反演回去得到：

f(x)=\sum_{x|d}g(d)\mu\left(\frac{d}{x}\right)=\sum_{x|d}\mu\left(\frac{d}{x}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor

此处默认n=min\left(n,m\right)\Rightarrow d\leqslant n

这里再次枚举 d是 n的多少倍

\sum_{x|d}\mu\left(\frac{d}{x}\right)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)\lfloor\frac{n}{ix}\rfloor\lfloor\frac{m}{ix}\rfloor=\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\mu(i)\frac{\lfloor\frac{n}{x}\rfloor}{i}\frac{\lfloor\frac{m}{x}\rfloor}{i}

到这里就已经可以上数论分块的套路了：

前面的\mu(i)直接预处理前缀和，然后分块使单次询问达到O\left(\sqrt{n}\right)。

杜教筛

作用：求解积性函数前缀和S(n)=\sum_{i=1}^nf(i)

套路：

构造一个g(n),得到

g(1)S(n)=\sum_{i=1}^nf*g-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)

并且这里f*g的前缀和与g的前缀和都比较好算, 在这里我们如果要求S(n)可以递归下去求解S(n/i)，g(i)是我们预先处理好的，这时可以使用数论分块的套路加速，另外S(n)预先也要处理好一部分，可以提高效率。

关于时间复杂度：

如果预处理好的部分大小为 K，时间复杂度为O\left(K+\frac{n}{\sqrt K}\right)，所以 K=n^\frac{2}{3})的时候时间复杂度最优为n^\frac{2}{3})。但是如果询问次数为Q，那么时间复杂度为O(K+\frac{Qn}{\sqrt{K}})所以要适当改一波K的大小，当然，我们不要直接按照对勾函数去算，因为杜教筛是一定要记忆化的,所以后面那部分是跑不满的，只要在询问次数多的时候适当改大一点就好。

式子的推导:

令

S(n)=\sum_{i=1}^nf(i)

\sum_{i=1}^nf*g=\sum_{i=1}^n\sum_{d|i}g(d)\times f(\lfloor\frac{i}{d}\rfloor)

=\sum_{i=1}^ng(i)\times\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)

关于这两个式子，用人话来说就是：1~n的所有数的所有因子都会贡献一个

\sum_{d|i}g(d)*f(\lfloor\frac{i}{d}\rfloor)

  • （ f和g下标相乘=i）

那么下面这个式子就很好理解了，第一维枚举这个因子,那么每一个

\sum_{i=1}^ng(i)*\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)

这里的i,j乘起来就唯一对应了1式中的一个i，他们是一一对应的，所以这个式子成立。

有了上面那个式子，就可以得到：

\sum_{i=1}^nf*g=\sum_{i=1}^ng(i)\times\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)=\sum_{i=1}^ng(i) \times S(\lfloor\frac{n}{d}\rfloor)

把i=1的提出来就可以得到

g(1)S(n)=\sum_{i=1}^nf*g-\sum_{i=2}^ng(i)S(\lfloor\frac{n}{i}\rfloor)

然后就没有然后了，上杜教筛就可以了

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<tr1/unordered_map>
#define ll long long
using namespace std;
tr1::unordered_map<int,int>m1;
tr1::unordered_map<ll,ll>m2;
const int N=6001000;//硬算出来是765w左右，但是因为记忆化可以略小一些
int block=6000000,mu[N],cnt,check[N],prim[N],n,T;
ll phi[N];
void get(int n){
    register int i,j;
    phi[1]=mu[1]=1;
    for(i=2;i<=n;i++){
        if(!check[i])mu[i]=-1,phi[i]=i-1,prim[++cnt]=i;
        for(j=1;j<=cnt&&i*prim[j]<=n;j++){
            check[i*prim[j]]=1;
            if(i%prim[j]==0){
                phi[i*prim[j]]=phi[i]*prim[j];break;
            }
            else{
                phi[i*prim[j]]=phi[i]*(prim[j]-1);
                mu[i*prim[j]]=-mu[i];
            }
        }
    }
    for(i=1;i<=n;i++)
        phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}
int djsmu(int n){
    if(n<=block)return mu[n];
    if(m1[n])return m1[n];
    int ans=1;
    for(int l=2,r;l<=n;l=r+1){
         r=n/(n/l);
         ans-=(r-l+1)*djsmu(n/l); 
    }
    return m1[n]=ans;
}
ll djsphi(ll n){
    if(n<=block)return phi[n];
    if(m2[n])return m2[n];
    ll ans=n*(n+1)/2;
    for(ll l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        ans-=(r-l+1)*djsphi(n/l); 
    } 
    return m2[n]=ans;
}
int main(){
    cin>>T;
    get(block);
    while(T--){
        cin>>n;
        cout<<djsphi(n)<<' '<<djsmu(n)<<'\n';
    }
    return 0;
}

min25筛

见我的另一篇博客

一些常见的求值

等幂求和

S_1(n)=\frac{n*(n+1)}{2}

S_2(n)=\frac{n*(n+1)(2n+1)}{6}

S_3(n)=\frac{n^2(n+1)^2}{4}=S_1(n)^2

关于[gcd(i,j)=1]

[gcd(i,j)=1]=\sum_{k|gcd(i,j)}\mu(k)=\sum_{k|i,k|j}\mu(k)

常见数论函数的拆分

欧拉函数：

\phi(ij)=\phi(i)\phi(j)\frac{gcd(i,j)}{\phi(gcd(i,j))}

莫比乌斯函数：

\mu(ij)=\mu(i)\mu(j)[gcd(i,j)=1]

约数个数：

d(ij)=\sum_{u|i}\sum_{v|j}[gcd(u,v)=1]

约数和：

\sigma(ij)=\sum_{u|i}\sum_{v|j}[gcd(u,v)=1](u*\frac{j}{v})

奇妙的狄利克雷卷积

1.

\phi*I=id

2.

\mu*id=\phi

3.

\mu*I=e

4.

I*I=d

^*5.

\mu^2*I=W(W(n)=2^{\text{n的质因子种类数}})

^*6.

W*I=d(n^2)

证明：设

n=p_1^{a_1}p_2^{a_2}……p_k^{a_k}

那么

d(n^2)=(2a_1+1)(2a_2+1)……(2a_k+1)

把这个式子拆开，一个质因子集合S的贡献就是

2^{|S|}\prod_{pi\in S}a_i

然后可以发现W*I的意义就是如此，一个2^{w(n)}被枚举的次数就是\prod_{pi\in S}a_i

^*7.

d^2*\mu=d(n^2)=\mu^2*d

证明1:

d(n^2)=\sum_{x_1|n}\sum_{x_2|n}[gcd(x_1,x_2)=1]

=\sum_{x_1|n}\sum_{x_2|n}\sum_{x_3|x_1,x_2}\mu(x_3)

=\sum_{x|n}\mu(x)d^2(\frac{n}{x})

=\mu*d^2

证明2:

d(n^2)=W*I=\mu^2*I*I=\mu^2*d

一些式子的化简与推导

1.

\sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor

证明：考虑容斥，右边的式子当i=1的时候就是全集n，然后依次减去含一个完全平方因子的，加上含两个完全平方因子的，减去含三个完全平方因子的....

2 .

\sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor=2*\sum_{i=1}^{\sqrt{n}}\lfloor \frac{n}{i} \rfloor-\lfloor\sqrt{n}\rfloor^2

证明：左式等价于\sum_{i=1}^{n}d(i)，类似于根号筛的思想，考虑一个数x的因子i会贡献i和\frac{x}{i},于是我们只枚举<=\sqrt{n}的部分再乘上一个2，但是这样如果i和\frac{x}{i}都<=\sqrt{n}就会被多算，减掉即可。

0%