积性函数和莫比乌斯反演

您也可以阅读体验更好、叙述更严谨的论文

积性函数

数论函数是指定义域在正整数、而值域在复数域上的一类函数,即\(f:\mathbb{Z}^{+}\rightarrow\mathbb{C}\)。

下文中的数论函数值域都在整数上。积性函数是一种特殊的数论函数,他们满足对于任意互质的一对数\(p,q\),有\(f(p)\cdot f(q)=f(pq)\),即他们的函数值乘起来等于他们乘起来的函数值。特别地,如果对于任意不互质两数上面的条件也成立,则称这个函数为完全积性函数

我们对两数$p,q$互质的定义为\(\gcd(p,q)=1\),所以我们称\(1\)和其他所有数都互质。于是我们可以知道对于一个积性函数\(f\),\(f(1)=1\)(除非它的所有函数值都是零)。

常用的积性函数

\(\mu(n)\),莫比乌斯函数。它的定义比较复杂,下面再写。

\(\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]\),欧拉函数,即在比不大于这个数的与他互质的数的个数。

\(d(n)=\sum_{i|n}1=\sum_{i=1}^{n}[i|n]\),约数个数。

\(\sigma(n)=\sum_{i|n}i=\sum_{i=1}^{n}[i|n]\cdot i\),约数和,即这个数的各个约数之和。

常用的完全积性函数

\(\epsilon(n)=[n=1]\),元函数,只在\(n\)为\(1\)时为\(1\),其他时候都为\(0\)。

\(I(n)=1\),恒等函数,他的值永远等于\(1\)。

\(id(n)=n\),单位函数。

莫比乌斯函数

莫比乌斯函数的定义严格地来写是这样的
我们设\(n\)分解后有\(k\)个质因数,他们是这样的\[n={p_1}^{s_1}\times {p_2}^{s_2}\times {p_3}^{s_3}\times\cdots\times {p_k}^{s_k}\]那么对应的莫比乌斯函数值就可以写成\[
\mu(n)=
\begin{cases}
0&(存在一个 s_i>1)\\
1&(k为奇数)\\
-1&(k为偶数)
\end{cases}
\]写成这样就是一个很直白的容斥系数了,所以我们就有\[
\sum_{d|n}\mu(d)=[n=1] \]怎么解释呢?如果\(n\)不是\(1\),那么它的因数就两两配对,一对因数的\(\mu\)要么都是\(0\)要么一个是\(1\)一个是\(-1\),求和就都是\(0\)了。

有了这个,再配合交换求和号的知识、整除分块和线性筛,顺便再充分理解一下约数和原数的大小关系之类的,你就可以解决很多没有毒瘤数据的数论裸题了。

线性筛求积性函数值

实际上,积性函数可以在线性筛的过程中顺便求出来,只要在找到质数的时候设置一下初值,然后筛去合数的过程中如果两个因数互质则直接乘起来,不互质则……

对于\(\mu\),这时\(p\times i\)出现了次数为\(2\)的项,我们直接赋成0就可以了;对于\(\varphi\),这个稍稍有点复杂,可以证明当\(p\)为质数且\(\gcd(p,i)\neq 1\)时有\(\varphi(p\times i)=\varphi(i)\times p\)。于是我们就可以写出下面的代码:

代码
int n;

bool flag[MaxN];
int primes[MaxN],pcnt;
int phi[MaxN],mu[MaxN];

flag[1]=false;
phi[1]=mu[1]=1;
for(int i=2;i<=n;i++)
    flag[i]=true;

for(int i=2;i<=n;i++){
    if(flag[i]){
        primes[++pcnt]=i;
        phi[i]=i-1;
        mu[i]=-1;
    }
    for(int j=1;j<=pcnt;j++){
        int p=primes[j];
        if(p*i>n)
            break;
        flag[p*i]=false;
        if(i%p==0){
            phi[p*i]=p*phi[i];
            break; // mu[i] = 0
        }else{
            phi[p*i]=phi[p]*phi[i]; // =phi[i]*(p-1)
            mu[p*i]=-mu[i];
        }
    }
}

狄利克雷卷积

狄利克雷卷积是一种将两个积性函数“卷起来”的一种操作,记作\(h=f*g\),它的结果仍然是一个积性函数:\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)\]这相当于枚举n的每一个约数,把相应的一对因数分别带进去求值乘起来,然后再都加起来。

狄利克雷卷积像一个普通的乘法一样,具有:
交换律:\(f*g=g*f\);
结合律:\((f*g)*h=f*(g*h)\);
分配律:\((f+h)*g=f*g+h*g\)。

对于狄利克雷卷积,我们有元函数卷上任意一个函数,结果还是那个函数,元函数扮演了单位元的角色。\[f*\epsilon=f\]

重写一些性质

我们可以把\(\mu\)的性质重写成卷积的形式:\[\mu*I=\epsilon\]\(\varphi\)也可以这样重写:\[\sum_{d|n}\varphi(d)=n\Longleftrightarrow\varphi*I=id\]

实际上,\(\mu\)和\(\varphi\)有着以下的奇妙关系:\[\frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}\]证明的话,只要把\(\varphi*I=id\)两边各卷上一个\(\mu\)然后把\(I*\mu\)结合成\(\epsilon\)就好了。

莫比乌斯反演

莫比乌斯反演定理:若\(F\)和\(f\)是两个数论函数,并且他们满足\[F(n)=\sum_{d|n}f(n)\]则有\[f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})F(d)\]证明类似,先写成\(F=f*I\)然后再两边卷上一个\(\mu\)即可得到\(F*\mu=f\)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注