莫比乌斯反演和数论函数

TopCarry · 2019-12-31 09:50:15 · 个人记录

前言

求解积性函数相关问题是数论中十分重要的一环，莫比乌斯反演则是求解积性函数相关的重要工具，当然各类筛法，常见的求值与化简也是数论问题的解题关键，本篇博客介绍了相关知识点以及记录了一些作者平时遇到的数论好题。

狄利克雷卷积

可以理解成两个函数间的乘法：

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

一些约定和记号

$2.$所有的除法表示取下整，没有打下整符号只是为了大家看的舒服和~~我写的方便~~。 $3.$一些常见的数论函数符号： $\mu(n):$莫比乌斯函数 $\phi(n):$欧拉函数 $I(n):$值恒等于$1$，方便构造狄利克雷卷积。 $e(n):$值为$[n=1]$，形如矩阵中的单位矩阵，任何函数与$e$进行狄利克雷卷积还是等于原函数。 $id(n):$值为$n$。 ### 莫比乌斯反演其实就下面这两个式子： $1.

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

\Updownarrow

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

证明1：

\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)

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

\Updownarrow

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

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

证明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)。

当然这比较naive，方便新学的同学理解，可以直接根据下面这个式子做，可以减少许多步骤：

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

杜教筛

作用：求解积性函数前缀和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的前缀和都比较好算

关于时间复杂度：

具体证明与本文无关且过于繁琐，略去，只要知道能做到<=n^{\frac{2}{3}}线性预处理，大于的部分根号筛复杂度便是O(n^\frac{2}{3})

拓展：

即便并不能构造出合适的狄利克雷卷积，碰到合适的式子也可以类似的筛，大于n^{\frac{2}{3}}的部分O(\sqrt{n})暴力并递归下去，小于的部分直接预处理出来，复杂度便是O(n^{\frac{2}{3}})。

式子的推导:

令

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:

#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)

对于和式(默认n<=m)：

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

另外特殊的有：

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

从欧拉函数的定义方面不难理解，因为二元组(1,1)重复所以减去一个1。

证明和一般形式的相等关系也不难：

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

=2\sum_{i=1}^n\sum_{d|i}\mu(d)\frac{i}{d}-1

=2\sum_{d=1}^n\mu(d)\sum_{i=1}^{\frac{n}{d}}i-1

=2\sum_{d=1}^n\mu(d)\frac{(1+\frac{n}{d})\frac{n}{d}}{2}-1

=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2+\sum_{d=1}^n\mu(d)\frac{n}{d}-1

=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2+\sum_{i=1}^n\sum_{d|i}\mu(d)-1

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

常见数论函数的拆分

欧拉函数：

\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})

奇妙的狄利克雷卷积

\phi*I=id

\mu*id=\phi

\mu*I=e

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

一些式子的化简与推导

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

证明：考虑容斥，右边的式子当i=1的时候就是全集n，然后容斥掉每一个能作为因子x^2的x，\mu是一个容斥系数，若某个数没有平方因子，那么它不会被容斥；否则将其最大的平方因子p^2，将p分解成a*b*c...的形式，相当于对于一个集合，有2^n-1种选择，若大小为奇数贡献是-1否则是1，所以这个集合的贡献必是-1。

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} 就会被多算，减掉即可。

\sum_{i=1}^ni*\frac{n}{i}=\sum_{i=1}^{n}S(\frac{n}{i})

\text{其中S(n)=}\sum_{i=1}^{n}i

证明：当i在S(j)中有贡献，那么j>=i，此处i<=\frac{n}{j} ，所以j\in[1,\frac{n}{i}]，故两式相等。

另外可以发现，上面两个式子就是前n个数的约数和。

max(a,b)=\sum_{i=1}^n[i<=a||i<=b]=n-\sum_{i=1}^n[a<i][ b<i]

看似没什么用其实可以帮助拆掉max

\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)f(i,j)=n*\sum_{i=1}^{n}\sum_{j=1}^{n}f(i,j)-\sum_{k=1}^{n}\sum_{i=1}^{k-1}\sum_{j=1}^{k-1}f(i,j)

当要求多组这样的f：

f(n)=\sum_{i=1}^{n}g(i)*h(\frac{n}{i})

设要求的组数和n同级别，那么暴力做复杂度就是O(n\sqrt{n})的。

但是可以发现，当n是一段连续区间的时候，某组g(i)和h(\frac{n}{i}) 才会同时出现，于是我们可以枚举a=i,b=\frac{n}{i}，然后把g(a)*h(b)的贡献添加到f的差分数组上。

这样复杂度就是调和级数，也就是O(nlogn) 。

相关题目：

列举拓展性比较强的几道题目。

[51nod1355]斐波那契最小公倍数

题目链接

solution:

考虑化lcm为gcd

ans=\prod f(a)*f(b)*f(c)*f(gcd(a,b))^{-1}*f(gcd(b,c))^{-1}*f(gcd(a,c))^{-1}*f(gcd(a,b,c))...

形式化的

d\text{的贡献}=f(d)^{\sum-1^{|T|+1}[gcd(T)=d]}

考虑直接把这个幂算出来，问题变成给定n个数，求有多少个奇/偶子集gcd为i。

我的做法是直接上容斥，对于每个数d容斥掉其倍数id的幂即可，注意这里幂的运算是在mod(P-1)的意义下进行，复杂度是调和级数的。最后在把每个fibonacci数乘上它的幂乘起来即可。

 #include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar()
inline int read(){
    register int x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
const int N=1010000,P=1e9+7;
int quickpow(int a,int b,int P){
    int ans=1,base=a;
    while(b){
        if(b&1)ans=1ll*ans*base%P;
        base=1ll*base*base%P;
        b>>=1;
    }
    return ans;
}
int f[N][2],n,m,tong[N],fib[N];
int main(){
    register int i,j;
    n=read();m=1e6;
    for(i=1;i<=n;i++)tong[read()]++;
    for(i=m;i>=1;i--){
        int cnt=0;
        for(j=i;j<=m;j+=i)
            cnt+=tong[j];
        if(cnt){
            f[i][0]=quickpow(2,cnt-1,P-1)-1;
            f[i][1]=f[i][0]+1;
            for(j=2*i;j<=m;j+=i){
                f[i][0]=(f[i][0]-f[j][0]+(P-1))%(P-1);
                f[i][1]=(f[i][1]-f[j][1]+(P-1))%(P-1);
            }
        }
    }
    fib[1]=1;
    for(i=2;i<=m;i++)fib[i]=(fib[i-1]+fib[i-2])%P;
    int ans=1;
    for(i=1;i<=m;i++){
        if(f[i][1]>=f[i][0])ans=1ll*ans*quickpow(fib[i],f[i][1]-f[i][0],P)%P;
        else ans=1ll*ans*quickpow(quickpow(fib[i],P-2,P),f[i][0]-f[i][1],P)%P;
    }
    cout<<ans;
    return 0;
}

[51nod1584]加权约数和

题目链接

solution:

首先考虑拆掉max，变成

n*f(n)-\sum_{i=1}^{n-1}f(i)

f(n)=\sum_{i=1}^n\sum_{i=1}^n\sigma(ij)

后面这个\sigma(ij)并不难拆开

f(n)=\sum_{i=1}^n\sum_{i=1}^n\sigma(ij)=\sum_{i=1}^n\sum_{i=1}^n\sum_{d|i}\sum_{D|j}[(d,D)=1]d*\frac{j}{D}

拆掉gcd(d,D)=1

\sum_{i=1}^n\sum_{i=1}^n\sum_{d|i}\sum_{D|j}\sum_{k|d,D}\mu(k)d*\frac{j}{D}

枚举k

\sum_{k=1}^{n}\mu(k)\sum_{d=1}^{n/k}dk*\frac{n}{dk}\sum_{D=1}^{n/k}S(\frac{n}{Dk})

整理一波

\sum_{k=1}^{n}\mu(k)k\sum_{d=1}^{n/k}d*\frac{n/k}{d}\sum_{D=1}^{n/k}S(\frac{n/k}{D})

后面两个和式是等价的，参见前面的【一些式子的化简和推导】

设

g(n)=\sum_{i=1}^{n}\mu(i)i

那么

f(n)=\sum_{i=1}^{n}g(i)*h(\frac{n}{i})

可以发现

h(n)=(\sum_{i=1}^{n}\sigma_1(i))^2

于是g,h都是可以线性筛的，处理出来即可。

至于要处理f，用前文写过的方法调和级数差分即可。

[51nod1222]最小公倍数计数

题目链接

solution:

这里我的方法会受到空间限制，并不能通过本题，但感觉拓展性比较强，就不记录正解的方法了。

设f(n)表示lcm=i的二元组个数，本题中就是要求f的前缀和。

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

w(i)=2^{i\text{的质因子个数}}

因为lcm本质是对应质因子的幂取max，i是对于每一个因子，大的幂减去小的幂得到的结果，这个w(i)其实是在划分每个因子的幂谁大谁小。

w(i)=\sum_{d|i}\mu^2(d)

ans=\sum_{d=1}^n\mu^2(d)\sum_{i=1}^{n/d}\frac{n/d}{i}

后面那个式子就是前\frac{n}{d}个数的因子数之和，所以前\frac{2}{3}n可以线性处理出来，大于\frac{2}{3}n的部分可以O(\sqrt{n})算。

前面式子的处理：

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

也可以前\frac{2}{3}n线性处理出来，大于\frac{2}{3}n的部分O(\sqrt{n})算。

时空复杂度参考杜教筛，为O(n^\frac{2}{3}) ，但是因为这题只有128M，处理的部分开不到n^\frac{2}{3}，故时间复杂度并不能保证。

[51nod1847] 奇怪的数学题

题目链接

solution:

第二大公约数等于最大公约数/最小公共因子，这个思路在很多题目中都有体现。

枚举最大公约数：

\sum_{d=1}^n(\frac{d}{minp(d)})^K\sum_{i=1}^\frac{n}{d}\sum_{i=1}^\frac{n}{d}[gcd(i,j)=1]

只要能筛出两边函数的前缀和，就可以数论分块解。

后面的\phi显然可以用杜教筛O(n^\frac{2}{3})的求解，对于前面的部分，我们发现它满足：

1.在x=prim的时候是完全积性的(f(x)=1)。

2.在x=prim^k的时候比较好求(f(x)=prim^{(k-1)*K})

我们发现洲阁筛可以在这个性质下O(\frac{n^\frac{3}{4}}{logn})的复杂度内求出所有f(\frac{n}{i})的点值，此题完毕。

闲话：

#### [SDOI2017数字表格] [题目链接](https://www.luogu.com.cn/problem/P3704) 枚举$gcd$顺便反演掉。 $$ ans=\prod_{i=1}^nfib(i)^{\sum_{j=1}^{n/i}\sum_{k=1}^{m/i}\sum_{d|j,k}\mu(d)}$$ $$=\prod_{i=1}^nfib(i)^{\sum_{d=1}^{n/i}\mu(d)\frac{n}{id}\frac{m}{id}} $$ 令$T=id

ans=\prod_{T=1}^{n}(\prod_{d|T}fib(d)^{\mu(\frac{T}{d})})^{\frac{n}{T}\frac{m}{T}}

只要能预处理出\prod_{d|T}fib(d)^{\mu(\frac{T}{d})}的前缀和就能整除分块了。

显然

f(n)=\prod_{T=1}^{n}(\prod_{d|T}fib(d)^{\mu(\frac{T}{d})})=\prod_{d=1}^nfib(d)^{S(\frac{n}{d})}

我们就是要求出f的前n项。

这个可以用本篇博客上面记载的技巧差分做到O(nlogn)，这样总复杂度就是O(nlogn+T\sqrt{n})。