引言

在数论问题中,积性函数有着广泛的应用。 如在莫比乌斯反演问题中,函数变换之后如何快速维护前缀和往往是最重要也是最难的一步。如果维护的函数具有积性,那就可以尝试利用线性筛在$O(n)$的时限内完成预处理,从而达到优化复杂度的神奇作用。 本文的大部分相关性质及公式来自: $《线性筛与积性函数》- 贾志鹏$ 博主将试着证明其中的性质公式,严谨性可能欠缺,其目的主要是帮助记忆和理解。 因水平有限 若有错误之处还望指出qwq~


积性函数的定义和性质

定义: 对于一个定义域为$N^{+}$的函数$f$,对于任意两个互质的正整数$a,b$,均满足$f(ab)=f(a)f(b)$,则称函数$f$为积性函数 若对于任意整数$a,b$都有$f(ab) = f(a)f(b)$,则函数$f$被称为完全积性函数。

性质(1)对于任意积性函数$f$,均有$f(1) = 1$

证明:因$1$与任何数都互质,假设存在一个正整数$a$满足$f(a)!=0$,故由定义:$$f(a) = f(1*a) = f(1)f(a)$$ 因$f(a)$不为$0$,故等号两端同时消去一个$f(a)$,得: $$f(1) = 1 $$ 证毕。

(2)对于一个大于$1$的正整数N,设$N = \prod p_i^{a_i}$,$p_i$为互不相同的素数。那么对于一个积性函数$f$来说,有: $$f(N) = f(\prod p_i^{a_i}) = \prod f(p_i^{a_i})$$ 若$f$完全积性,则$$f(N) = \prod f(p_i)^{a_i}$$

证明:由积性和完全积性的定义易得。


欧拉函数$\varphi$

定义:对于正整数$n$,$\varphi(n)$是小于n的正整数中与n互质的个数。

定义式:若’$n = \prod p_i^{a_i}$’ $$\varphi(n) = n \prod(1 - \frac{1}{p_i})$$

性质(1)欧拉函数为积性函数,而不是完全积性函数。

证明:设两个互质的正整数$n,m$ 则:

$\varphi(n) = n \prod(1 - \frac{1}{p_i})$

$\varphi(m) =m \prod(1 - \frac{1}{p’_i})$

$\varphi(n)\varphi(m) = n \prod(1 - \frac{1}{p_i})m \prod(1 - \frac{1}{p’_i}) = nm\prod(1 - \frac{1}{p_i})(1 - \frac{1}{p’_i})$

因$n,m$互质,故 $p_i,p’_i$ 各不相同,且均为$nm$的质因子。

故推出: $\varphi(nm) = \varphi(n)\varphi(m)$ 积性函数性质得证。 而完全积性由上证明可见,$n,m$互质是一个严格且不可或缺的条件,可见,欧拉函数不是完全积性函数。

(2)假设存在一个素数$p$和一个正整数$k$,则:$\varphi(p^k) = p^k - p^{k-1}$

证明:

可以从反面来思考这件事,在小于$p^k$且与其不互质的数有以下形式:

$ p*1,p*2,…p * ( p^{k-1} - 1) $ (因为p是唯一的质因子)

故由定义:$\varphi(p^k) = $总数 - 不互质的数 = $(p^k-1) - (p^{k-1} -1) = p^k - p^{k-1}$ 证毕。

另外还可以从定义式出发去理解这个结论。 $$\varphi(p^k) = p^k(1-\frac{1}{p}) = p^k - p^{k-1}$$

(3)欧拉定理:若有互质的两个正整数$a,n$,则有$a^{\varphi(n)} \equiv 1(mod \ n)$ 此定理常用来求解逆元。

证明:(可参考百度百科

(4)假设存在一个正整数n,则:$\sum_{d|n} \varphi(d) = n$

证明: 先考虑特殊情况: $n = 1$时 $\varphi(1) = 1$ 显然成立

对于一般情况,$n$一定可以质因数分解为:

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

当n只含一个质因子时,即$n = p^a$

有:

$$ \sum_{d|n}\varphi(d) = \sum_{i = 0}^a \varphi (p^i) = 1 + \sum_{i=1}^{a}( p^i - p^{i-1}) = 1 + \sum_{i=1}^a(-p^{i-1} + p^i)$$

显然,将求和式展开,会有一些项可以合并。

比如$a = 3$时,原式等于: $$1 - p^0 + p^1- p^1 + p^2 - p^2 + p^3 = p^3 $$

可见:

$$\sum_{d|n}\varphi(d) = \sum_{i=0}^a \varphi(p^i) = p^a = n$$

当$n$含多个质因子时,即

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

利用积性函数的性质有:

$$\sum_{d|n}\varphi(d) = \sum_{i=0}^{a_1} \varphi(p_1^i)\sum_{i=0}^{a_2} \phi(p_2^i) …… \sum_{i=0}^{a_k} \varphi(p_k^i)$$

同上易得: $$原式=p_1^{a_1}p_2^{a_2} …… p_k^{a_k} = n$$ 证毕。

(5)当$n>1$,小于$n$且与$n$互质的数之和为$$sum = \frac{n\varphi(n)}{2}$$

证明:在数论求$gcd$中,有两个非常出名的公式,基于这两个公式,出现了两种快速求$gcd$的方法,更相减损法和辗转相除法。这两个公式是:(假设有两个正整数$a,b$且满足 $a>b$) $gcd(a,b) = gcd(a,a-b)$ 和 $gcd(a,b) = gcd(b,a\%b)$

由第一个公式,知: 若$m$与$n$互质,则$n-m$也一定与$n$互质。 这样就能将保证当$n>2$时,$\varphi(n)$一定为偶数,且可两两配对,每一对的和都是$n$。 故$$sum = n\frac{\varphi(n)}{2} $$ 当$n=2$时,代入验证知,此公式依然满足。

证毕。

例题:HDU 3501 题意:求小于n且与n不互质的数之和。 思路:直接利用公式求反面,总数 - 反面数即为答案。 代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;

const int mod = 1000000007;
const int A = 1e5 + 10;
bool vis[A];
int pri[A],tot;

void init(){
    tot = 0;
    vis[0] = vis[1] = 1;
    for(int i=2 ;i<A ;i++){
        if(vis[i] == 0) pri[++tot] = i;
        for(int j=1 ;j<=tot&&pri[j]*i<A ;j++){
            vis[pri[j]*i] = 1;
            if(i%pri[j] == 0) break;
        }
    }
}

int main(){
    init();
    ll n;
    while(~scanf("%I64d",&n) && n){
        ll ans = (n*(n-1)/2)%mod;
        ll res = n,m = n;
        for(int i=1 ;i<=tot&&pri[i]*pri[i]<=n ;i++){
            if(n%pri[i] == 0){
                res = res/pri[i]*(pri[i]-1);
                while(n%pri[i] == 0) n/=pri[i];
            }
        }
        if(n!=1) res = res/n*(n-1);
        ans = ans - res*m/2;
        printf("%I64d\n",(ans%mod+mod)%mod);
    }
    return 0;
}

莫比乌斯函数$\mu$

定义式:

$$ \mu(n) = \begin{cases} 1 & (n=1)
(-1)^k&(n=p_1p_2…p_k)
0&(else)
\end{cases}$$

性质: (1)对于任意正整数n,有: $$\sum_{d|n} \mu(d) = [n == 1]$$

该性质在莫比乌斯反演中有着极大应用。

证明: 当$n = 1$时 等式显然成立。 当$n>1$时,令

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

考虑莫比乌斯函数取值的特殊性,若函数值不为$0$,则d只含每个质因子的$0$次或$1$次项。 故

$$\sum_{d|n}\mu(d) = C_k^0 - C_k^1 + C_k^2 …+(-1)^kC_k^k = \sum_{i=0}^k(-1)^iC_k^i$$

由二项式定理,原式等于:

$$\sum_{i=0}^k(-1)^iC_k^i = \sum_{i=0}^kC_k^i(-1)^i(1)^{k-i} = (-1 + 1)^k = 0$$

综上所述: 当$n=1$原式为$1$ 当$n>1$原式为$0$ 证毕。

(2)对于任意正整数$n$,有: $$\sum_{d|n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}$$

证明: 令$f(n)$满足:$f(n) = \sum_{d|n}\varphi(d)$

由欧拉函数的性质$(4)$:$f(n) = n$ 又由莫比乌斯反演:

$$\varphi(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$$

推出:

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

等式两边同除以n,得: $$\frac{\varphi(n)}{n} = \sum_{d|n}\frac{\mu(d)}{d} $$ 证毕。


线性筛求积性函数

欧拉函数$\varphi$

考虑将所有数分成三类: (1)质数 $\varphi(i) = i - 1$

(2)最小质因子指数为1:$\varphi(i*p) = \varphi(i) \varphi(p)$

(3)最小质因子指数大于1:$\varphi(i*p) = p*\varphi(i)$

(可从欧拉函数的定义式出发)

代码:

void init(){
    tot = 0;phi[1] = 1;
    for(int i=2 ;i<A ;i++){
        if(!vis[i]){pri[++tot] = i;phi[i] = i-1;}
        for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
            vis[i*pri[j]] = 1;
            if(i%pri[j] == 0){
                phi[i*pri[j]] = pri[j] * phi[i];break;
            }
            phi[i*pri[j]] = phi[pri[j]] * phi[i];
        }
    }
}

莫比乌斯函数$\mu$

因为线性筛每次都是用最小质因子去筛每一个数。 故也可分为三类: (1)$i$为质数:$\mu[i] = -1$

(2)$i$已经包含最小质因子$p$:$\mu[i*p] = 0$

(3)$i$不包含最小质因子$p$ :$\mu[i*p] = -\mu[i]$

代码:

void init(){
    tot = 0;mu[1] = 1;
    for(int i=2 ;i<A ;i++){
        if(!vis[i]){pri[++tot] = i;mu[i] = -1;}
        for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
            vis[i*pri[j]] = 1;
            if(i%pri[j] == 0){mu[i*pri[j]] = 0;break;}
            mu[i*pri[j]] = -mu[i];
        }
    }
}

以下为其他常见积性函数的线性筛:

约数个数函数$d$

仍然分三类讨论,此时我们还需要维护每一个数$i$最小质因子的指数$cnt[i]$

(1)$i$为质数:

$d[i] = 2 $

$cnt[i] = 1$

(2)$i$已经包含最小质因子$p$:

$d[i*p] = d[i]/(cnt[i]+1)*(cnt[i]+2) $ (由约数个数公式易得)

$cnt[i*p] = cnt[i] + 1$

(3)$i$不包含最小质因子$p$ :

$d[i*p] = d[i]*(cnt[p] + 1) = d[i]*2 $

$ cnt[i*p] = 1$

代码:

void init(){
    tot = 0;d[1] = 1;
    for(int i=2 ;i<A ;i++){
        if(!vis[i]){pri[++tot] = i;d[i] = 2;cnt[i] = 1;}
        for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
            vis[i*pri[j]] = 1;
            if(i%pri[j] == 0){
                d[i*pri[j]] = d[i]/(cnt[i]+1)*(cnt[i]+2);
                cnt[i*pri[j]] = cnt[i] + 1;
                break;
            }
            d[i*pri[j]] = d[i]<<1;
            cnt[i*pri[j]] = 1;
        }
    }
}

约数和函数$\sigma$

假设一个正整数$n$分解质因子之后为:

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

$$\sigma(n) = \sum_{i = 0}^{a_1}p_1^i \sum_{i=0}^{a_2}p_2^i….. \sum_{i=0}^{a_k}p_k^i$$

假设最小质因子为$p_1$

故线性筛中每一个被筛到的数比起原来的数,差别只在于:

$\sum_{i=0}^{a_1} p_1^i$

故我们可以维护两个量:

$sum[i]:i$的最小质因子$p_1$贡献的和:$\sum_{i=0}^{a_1} p_1^i$

$Mx[i]:$ $p_1^{a_1}$ $a_1$ 为最小质因子的最高次数。

然后又可以把所有数分成三类:

(1)$i$为质数:

$\sigma[i] = i+1 $ $sum[i] = i+1$ $Mx[i] = i$

(2)$i$已经包含最小质因子$p$:

$\sigma[i*p] = \sigma[i]/sum[i]*(sum[i]+Mx[i]*p) $

$sum[i*p] = sum[i] + Mx[i]*p$

$Mx[i*p] = Mx[i]*p$

(3)$i$不包含最小质因子$p$ :

$\sigma[i*p] = \sigma[i]*\sigma[p]= \sigma[i]*(p+1) $

$ sum[i*p] = p+1$

$Mx[i*p] = p$

代码:

void init(){
    tot = 0;Sigma[1] = 1;
    for(int i=2 ;i<A ;i++){
        if(!vis[i]){
            pri[++tot] = i;
            Sigma[i] = 1 + i;
            sum[i] = 1 + i;
            Mx[i] = i;
        }
        for(int j=1 ;j<=tot&&i*pri[j]<A ;j++){
            vis[i*pri[j]] = 1;
            if(i%pri[j] == 0){
                Sigma[i*pri[j]] = Sigma[i]/sum[i]*(sum[i] + Mx[i]*pri[j]);
                sum[i*pri[j]] = sum[i] + Mx[i]*pri[j];
                Mx[i*pri[j]] = Mx[i]*pri[j];
                break;
            }
            Sigma[i*pri[j]] = Sigma[i]*(pri[j] + 1);
            sum[i*pri[j]] = pri[j] + 1;
            Mx[i*pri[j]] = pri[j];
        }
    }
}