积性函数与迪利克雷卷积

前言：

早睡早起身体好！今天更一下积性函数。
 

积性函数的定义：

什么是积性函数呢？（又叫乘性函数）
 
先讲一个更宽泛的概念，算术函数。（算术函数又称数论函数）
算数函数，就是对所有正整数定义的函数，也就是定义域为正整数的函数。
 
而积性函数，则是一种特殊的算术函数。
 
对于函数$f(x)$，
若满足$f(1)=1$，
且对于任意互质的正整数$p$和$q$，满足$f(pq)=f(p)f(q)$，
则称$f(x)$为积性函数。
 
而对于函数$f(x)$，
若满足$f(1)=1$，
且对于任意的正整数$p$和$q$，满足$f(pq)=f(p)f(q)$，
则称$f(x)$为完全积性函数。
（这不是我们这里要讲的重点）
 
我们主要来讲积性函数，现在继续来看这个定义。
根据唯一分解定理，我们可以将$x$分解得到$x=p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$。
则有$f(x)=f(p_1^{k_1})f(p_2^{k_2})\dots f(p_n^{k_n})$。
也就是说，当我们想要定义一个积性函数时，我们只要将质数的幂次都定义好，那么所有数的函数值都已经得到了。
 
现在，我们可以自己捏一个没什么用的积性函数出来了。
我们定义$f(x)=\{\begin{array}{ll}1& \text{,}x=1\\ p\times k& \text{,}x=p^k,p是质数，k是正整数\end{array}$
然后再说明当$a\perp b$时，$f(ab)=f(a)f(b)$即可。（$a\perp b$表示$a$与$b$互质）
没什么用的积性函数就捏好了。
 
 
 

常见的积性函数：

现在讲一些有用的积性函数。

单位函数和常数函数：

先来两个显然的积性函数。
 
第一个是单位函数$e(n)=[n=1]$，
（中括号$[]$表示逻辑运算，当括号内表达式成立，则值为$1$，反之为$0$）
也就是说，当$x=1$时，$e(x)=1$；当$x\ne 1$时，$e(x)=0$。
可以理解它为单位元，后面会有更深的理解。
 
第二个是常数函数$1(n)=1$。
咳咳，这里第一个$1$是函数符号，不要问我为什么这么表示。
这个函数就是，对于任意的$x$，均满足$1(x)=1$。
 
当然这两个函数都是完全积性函数，这不是重点，我们继续。
 

欧拉函数$\phi (n)$：

欧拉函数$\phi (n)$，表示小于等于$n$且与$n$互质的数的个数。
比如小于等于$6$，并且和$6$互质的数有$1$和$5$，所以$\phi (6)=2$。
 
这个函数的用处就多了去了，要单独开一篇博客讲，这里就只证明一下它是积性函数。
因为不会证，所以这里要用一下循环论证。
姑且记住它是积性函数吧，留的坑等讲它的时候再填。
提一点，$\phi (p^k)=p^k-p^{k-1}$，其中$p$是质数，$k$是正整数。
 

因子和与因子个数：

因子和函数$\sigma (n)$，表示$n$的因子和，有$\sigma (n)={\sum }_{d|n}d$。
因子个数函数$\tau (n)$，表示$n$的因子和，有$\tau (n)={\sum }_{d|n}1$。
证明这两个是积性函数，有兴趣可以自证。
这里${\sum }_{d|n}$就是枚举$n$的所有因子$d$。
看公式也比较明白。因子和就是枚举所有因子$d$，然后把所有因子$d$加起来。因子个数就是枚举所有的因子，然后对于每个因子都加一个$1$。
 
同样举一下，
$\sigma (p^k)=1+p+p^2+\dots +p^k=\frac{p^{k+1}-1}{p-1}$，
$\tau (p^k)=k+1$，
这两个都比较容易得出来。
 

莫比乌斯函数$\mu (n)$：

又是一个大神级别的函数，也是要单独开一篇来讲的，先说定义。
$\mu (n)=\{\begin{array}{ll}1& \text{,}x=1\\ (-1{)}^r& \text{,}x=p_1{p}_2\dots p_r,即x的所有素因子次数均为1,其中r表示素因子个数\\ 0& \text{,}其他情形,即x存在平方因子\end{array}$
 
这个定义就离谱，后面会讲它的由来的。
现在也同样只要知道它是积性函数。
 
 

积性函数筛：

要知道一点，积性函数都是可以$o(n)$筛出来的。
（当然，只需要求某一个函数值的时候，是可以有差不多$o(\sqrt{n})$的做法更快得到的，而筛就是筛出$1$到$n$的积性函数值）
 
那么具体怎么筛？
首先，积性函数筛都是建立在$o(n)$素数筛的基础上的。

先讲线性素数筛。
线性素数筛就是在埃式筛的基础上进行了改进——让每一个数只被一个数给筛掉。
我们知道，埃式筛是用每一个素数，去筛它的倍数。而线性筛，则要保证每个数只被它最小的素因子给筛掉。
直接上代码。

int notPrime[MAXN],prime[MAXN],tot;
void getPrime(int n)
{
    
    notPrime[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}

解释一下这个代码的原理。
首先，所有的合数都可以表示成另一个数乘上它的最小素因子。
所有我们得到一个数后，只要枚举选用哪个素数作为它的最小素因子即可。
那么这个代码，先是枚举每一个数$i$，如果没有被筛过，那就丢到素数列表$prime[]$里。
然后对于这个数$i$，我们还要做的一件事，就是枚举它要乘上的最小素因子$prime[j]$。
当$i$这个数，能够整除当前这个素因子，那么就不能再往后枚举了。因为当前这个因子是$i$的一个素因子了，如果我们再往后枚举的话，就比这个素因子要大了，那就不是用最小素因子筛的了。
到这里代码就结束了。
 
 
现在我们来讲积性函数筛。
其实就是在素数筛的基础上进行改进。
首先，对于积性函数$f(x)$，我们要具备快速算出$f(p^k)$的能力，就跟我们之前定义的时候说的一样，然后根据积性函数的性质，来得到其他的函数值。
做的时候，我们在筛出每个数的位置算它的积性函数值$f(x)$。
首先，筛出质数的时候，我们直接把质数p的函数值$f(p)$赋上。
然后在循环里筛合数时，有两种情况，一种是$i$不能被$prime[j]$整除的，那么就有$gcd(i,prime[j])=1$成立，得到$f(i\times prime[j])=f(i)f(prime[j])$。
那么就只剩最后一种情况，就是$i$能被$prime[j]$整除的情况，这时候我们处理出$i$中最小素因子的幂次$lo{w}_i$，就有$gcd(\frac{i}{lo{w}_i},prime[j]\times lo{w}_i)$，就可以得到$f(i\times prime[j])=f(\frac{i}{lo{w}_i})f(prime[j]\times lo{w}_i)$。
最后，想办法处理$lo{w}_i$就好了，这个也可以在筛的时候处理。因为我们是拿最小素因子筛的，所以有$low(i\times prime[j])=low(i)\times prime[j]$。
到这里，就大功告成了。
上模板。（这个板子现写的，可能不会有问题）

int notPrime[MAXN],prime[MAXN],tot,low[MAXN];
int f[MAXN];
void getFunc(int n)
{
    
    notPrime[1]=f[1]=low[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])low[i]=prime[tot++]=i,f[i]=(素数直接计算);
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])
            {
    
                low[i*prime[j]]=prime[j];
                f[i*prime[j]]=f[i]*f[prime[j]];
            }
            else 
            {
    
                low[i*prime[j]]=low[i]*prime[j];
                if(low[i]==i)f[i*prime[j]]=(素数幂次直接计算);
                else f[i*prime[j]]=f[i/low[i]]*f[prime[j]*low[i]];
                break;
            }
        }
    }
}

 
 
上面是一般的积性函数求法。
现在讲讲特殊的，欧拉函数和莫比乌斯函数的筛法。
原理还是一样，只不过有些地方比较便捷。
 
先说莫比乌斯函数。
首先质数$p$的函数值$\mu (p)=-1$。
那么当$i$不被$p$整除时，求法一样，直接用积性函数性质，$\mu (ip)=\mu (i)\mu (p)=-\mu (i)$。
当$i$被$p$整除时，（我们知道，当$x$存在平方因子时，$\mu (x)=0$），就可以大胆的赋上$0$了。
模板：

int notPrime[MAXN],prime[MAXN],tot;
int mu[MAXN];
void initMu(int n)
{
    
    notPrime[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
    mu[i*prime[j]]=0;break;}
        }
    }
}

 
然后是欧拉函数，
质数时，$\phi (p)=p-1$。
然后它有个神奇的性质，对于一个质数$p$，若$p|i$，则$\phi (ip)=\phi (i)p$；若$p$不整除$i$，则$\phi (ip)=\phi (i)(p-1)$。
然后根据这个，又可以很容易地写出欧拉函数筛。

int notPrime[MAXN],prime[MAXN],tot;
int phi[MAXN];
void initPhi(int n)
{
    
    notPrime[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,phi[i]=i-1;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else {
    phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
}

 
积性函数筛讲完了。
 
 

迪利克雷卷积：

在讲之前，再给出几个数论函数。（注意数论函数和积性函数的区别）
$id(n)=n$，表示自身函数，函数值等于自变量本身。
$\omega (n)={\sum }_{p|n}1$，其中$p$是素数，函数值表示$n$的素因子个数。
 
 
开讲开讲。
迪利克雷卷积运算是数论函数的重要运算法则。
对，是运算法则，就像加减乘除一样的运算法则。
而且是函数的运算法则，运算结果也是一个函数。
你可以这么理解，这是专门为数论函数而建立的一种运算机制。
 
我们将数论函数$f$和数论函数$g$，进行迪利克雷卷积运算后，得到一个新的数论函数$h=f\ast g$。（这里的$\ast$不是乘号，而是卷积运算的符号）
那么怎么个运算法呢。
那就是卷积的定义式$h(n)=(f\ast g)(n)={\sum }_{d|n}f(d)g(\frac{n}{d})={\sum }_{d|n}f(\frac{n}{d})g(d)$。
 
现在来看这个式子，${\sum }_{d|n}$应该不陌生了，就是枚举因子。
我们回过来看前面的两个式子。
因子个数$\tau (n)={\sum }_{d|n}1$，我们发现这个函数其实就是两个常数函数通过卷积运算得到的。
我们就得到了一个式子$\tau =1\ast 1$。
那么同理，再看因子和$\sigma (n)={\sum }_{d|n}d$，就有了$\sigma =1\ast id$。

到这里，应该了解了一些简单的卷积运算。
还要知道几个关于迪利克雷卷积运算的性质。
首先，它满足交换律，结合律。
然后，对于任意数论函数$f$，有$f\ast e=f$，即单位函数是一个单位元。
还有，若$f$是积性函数，且$g$是积性函数，则$f\ast g$也是积性函数。

卷积运算大概就是这样了。
现在再罗列一些函数之间的卷积关系。
$\tau =1\ast 1$
$\sigma =1\ast id$
$1\ast \mu =e$
$\phi \ast 1=id$
$\phi =id\ast \mu$
 
前两个式子前面讲过了，就不讲了。
 
你会发现第三个式子是一个神奇的式子，莫比乌斯函数卷上常数函数居然是单位元，换句话说，$\mu$和$1$互为逆元。
其实这就是我们前面埋的一个坑，关于莫比乌斯函数那离谱的定义。
你可以理解成，它就是用来构造成常数函数的逆元的，这样做就可以实现莫比乌斯反演，后面一章博客会讲。
这样一来，还可以再得到一些式子，例如$\tau \ast \mu =1$，$\sigma \ast \mu =id$等等，即在等式两边同时乘上$\mu$与$1$抵消掉。
 
我们再看最后两个式子，其实就是同一个式子，根据前面$1$和$\mu$的逆元关系进行了变换。
至于为什么$\phi =id\ast \mu$，这个式子很重要，会在后面的莫比乌斯反演里讲。
 
 
 
这课码了6000字，难顶，终于讲完了。