数论函数

· · 个人记录

数论函数

定义域为正整数（或整数）、而函数值在复数域中取值的函数称为 数论函数。

积性函数

设 f 为数论函数且当 \gcd(a,b)=1 时，有 f(a)\times f(b)=f(a \times b)，则称 f 为积性函数

容易看出，对于任何积性函数有 f(1)=1

特别的，若数论函数 f 对于任何 a,b 都有 f(a)\times f(b)=f(a\times b)，则称 f 为完全积性函数。

容易看出，若 f 为积性函数，且 n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s} 是 n 的标准分解，则有

f(n)=f({p_1}^{a_1})f({p_2}^{a_2})\dots f({p_s}^{a_s})

利用上式，大部分积性函数可以用欧拉筛进行求值

线性筛（欧拉筛）

略

一些有用的函数

单位函数 \epsilon 的定义为 \epsilon (n)=[n=1]

这里 [\ ] 的含义为：若 [\ ] 内的条件为真则为 1 ，否则为 0

显然，单位函数是积性函数

除数函数 \sigma_k(n) 表示 n 的因子的 k 次方之和

形式化的， \sigma_k(n)=\sum\limits_{d|n}d^k

n$ 的约数个数 $\sigma_0(n)$ 常记为 $d(n)$，约数和 $\sigma_1(n)$ 常记为 $\sigma(n)

除数函数是积性函数

幂函数 Id_k(n)=n^k ， Id=Id_1

一般的，1 表示取值恒为 1 的常函数

欧拉函数

定义

$\displaystyle\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]

计算

通过容斥原理可以得到

\displaystyle\varphi (n)=n\prod\limits_{i=1}^{s} (1- \frac{1}{p_1})

其中 n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s} 是 n 的标准分解

时间复杂度 \mathcal{O(\sqrt{n})}

int phi(int x){
    int ans=x;
    for (int i=2;i*i<=x;i++){
        if (x%i==0){
            ans=ans/i*(i-1);
            while (x%i==0) x/=i;
        }
    }
    if (x>1) ans=ans/x*(x-1);
    return ans;
}

可以利用 欧拉筛 在 \mathcal{O(n)} 的时间内计算 \varphi 在 1 到 n 处的取值

memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
sum[1]=phi[1]=1;

for (int i=2;i<=MAXN;i++){
    if (prime[i]){
        primes[++tot]=i;
        phi[i]=i-1;
    }

    for (int j=1;j<=tot&&primes[j]*i<=MAXN;j++){
        prime[i*primes[j]]=false;
        if (i%primes[j]==0){
            phi[i*primes[j]]=phi[i]*primes[j];
            break;
        }
        else phi[i*primes[j]]=phi[i]*(primes[j]-1);
    }
}

性质1

当 $n,m$ 互质时，满足: $\varphi(n*m)=\varphi(n)*\varphi(m)$ 那么显然，当 $n$ 根据算术基本定理分解为 $n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}$ 时： $\displaystyle\varphi(n)=\prod_{i=1}^m\varphi(p_i^{c_i})
证明：

若 n 与 m 互质，则 n 与 m 没有相同的质因子

设 n 的质因子个数为 cnt_n，的质因子个数为 cnt_m ，则

\displaystyle\varphi(n)\times\varphi(m)=n\times\prod_{i=1}^{cat_n}(1-p_i)\times m\times \prod_{i=1}^{cnt_m}*(1-p_i)=n\times m\prod_{i=1}^{cnt_n+cnt_m}(1-p_i)=\varphi(nm)

证毕。

性质2

对于质数 p，它的欧拉函数值 \varphi(p)=p-1

证明：

因为 p 为质数，所以比它小的数都和它互质，即在 1\sim p 有 p-1 个数和它互质。

证毕。

性质3

当 n 为奇数时, \varphi(2\times n)=\varphi(n)

证明：

当 n 为奇数时，n 与 2 互质

由欧拉函数是积性函数可知， n 与 2 互质时， \varphi(2n)=\varphi(2)\times\varphi(n) 又因为 \varphi(2)=1 所以 \varphi(2\times n)=\varphi(n)

证毕。

性质4

当 n=p^k 时，\varphi(n)=p^k-p^{k-1}

证明

因为 n=p^k ,所以 n 只有 p 一个质因数，则由欧拉函数的计算式可得

\varphi(n)=p^k*(1-\frac{1}{p})=p^k-p^{k-1}

证毕。

性质5

n$ 中与 $n$ 互质的数的和为 $\varphi(n)\div 2\times n\quad (n\gt 1) ##### 证明： 需要知道的一个基本事实是 $\gcd(n,x)=\gcd(n,n-x)\quad (n\gt x)$ （辗转相减法） 因为 $\gcd(n,x)=\gcd(n,n-x)\quad (n\gt x)$，所以**与 $n$ 互质的数都是成对出现的** 每一对的和都为 $n$ 。所以他们的和为 $\varphi(n)\div 2\times n$ 。 至于 $\varphi(n)\quad (n \gt 2)$ 为偶数。因为与 $n$ 互质的数都是成对出现的，所以显然与 $n$ 互质的数为偶数，即 $\varphi(n)$ 为偶数。 证毕。 #### 性质6 若 $p|n$ 且 $p^2|n$ ，$\varphi(n)=\varphi(\frac{n}{p})*p

若 p|n 且 p^2\nmid n ，\varphi(n)=\varphi(\frac{n}{p})*(p-1)

证明：

对于第一点

若 p|n 且 p^2|n ，则证明 n 和 \frac{n}{p} 有相同的质因子，只是 p 这一项的指数不同

那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：

\displaystyle\frac{n\prod\limits_{i=1}^{m}(1-\frac{1}{p_i})}{\frac{n}{p}\prod\limits_{i=1}^{m}(1-\frac{1}{p_i})}=\frac{n}{\frac{n}{p}}=p

对于第二点

若 p|n 且 p^2 \not| \, n ，则说明 p 与 \dfrac{n}{p} 互质（因为 p 为素数）

那么根据欧拉函数为积性函数的这个性质即可证得 \varphi(n)=\varphi(\frac{n}{p})*\varphi(p)=\varphi(\frac{n}{p})*(p-1)

证毕。

这个性质广泛用于递推求欧拉函数

性质7

对于任意 n ，有

n=\sum\limits_{d|n}\varphi(d)
证明1:

设 f(n)=\sum\limits_{d|n}\varphi(d)，则 f(n) 是一个积性函数

证：

\begin{aligned} f(n)\times f(m) &= \sum\limits_{i|n}\varphi(i) \sum\limits_{j|m} \varphi(j)\\ &= \sum\limits_{i|n}\sum\limits_{j|m}\varphi(i)\times\varphi(j)\\ &= \sum\limits_{i|n}\sum\limits_{j|m}\varphi(i\times j)\\ &= \sum\limits_{d|nm} \varphi(d)\\ &=f(nm) \end{aligned}

可以发现的是，\sum\limits_{i|n}\sum\limits_{j|m}\varphi(i\times j) 涵盖了所有 nm 的因数的欧拉函数，即为 f(n)\times f(m), 所以 f 是一个积性函数

那么则有

若 n 根据算数基本定理可以分解为 {p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}，由 f 是一个积性函数可知，

f(n)=f({p_1}^{a_1})f({p_2}^{a_2})\dots f({p_s}^{a_s})

所以 f(p^a)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^a)=1+(p-1)+(p^2-p)+\cdots+(p^a-p^{a-1})=p^a

则 f(n)=f({p_1}^{a_1})f({p_2}^{a_2})\dots f({p_s}^{a_s})={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}=n

即 n=\sum\limits_{d|n}\varphi(d)

证毕

证明2：这个性质的证明需要我们从 1 到 n 中的所有整数按照与 n 的 gcd 来分类。

若 gcd({n},{i})={d}，那么 gcd(\frac{n}{d},\frac{i}{d})=1。而又因为 \frac{i}{d}\le\frac{n}{d} 且 \frac{i}{d} \in N^* ，故这样的 i 有 \varphi(\frac{n}{d})个。

我们考虑所有的 d|n 时，也就同时考虑到了所有 1 到 n 之间的所有 d ，所以就有了下面这个式子：

n=\sum\limits_{d|n}\varphi(\frac{n}{d})=\sum\limits_{d|n}\varphi(d)

证毕。

数论分块

是非常常用的东西 所以有必要讲一讲

数论分块适用于这样的形式：

\sum\limits_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor

我们发现有许多的 \left\lfloor \frac{n}{i} \right\rfloor 值是相同的，相同的值形成了一个个连续的块，所以可以用数论分块来加速求和过程，复杂度 \mathcal{O(\sqrt{n})} 。

附代码

for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}

其中 ans+=(r-l+1)*(n/l); 的意义为 有长度为 r-l+1 的块的值为 n\l 。

顺带一提，这个式子可以化为

\sum\limits_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor = \sum\limits_{k=1}^{n}d(k)

这里 d(k) 是前文提到过的表示约数个数的函数

由于 d 可以用欧拉筛预处理出来，而这个式子就是 d 的前缀和，所以可以在线性时间内预处理出来。

当然，并不是所有可以用数论分块解决的问题都可以这样在线性时间内预处理（比如在求和的时候乘个什么东西 是很常见的形式），这就是数论分块的意义所在。

Dirichlet 卷积

定义

设 f,g 是数论函数，且数论函数 h 满足

h(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})

则称 h 为 f,g 的 Dirichlet 卷积， 记作 h=f*g

性质

对于任意数论函数 f ，有 f = f * \epsilon = \epsilon * f，即单位函数 \epsilon 是 Dirichlet 卷积的 单位元。

Dirichlet 卷积满足 交换律和结合律

若 f,g 为积性函数，则 h=f * g 也是积性函数

应用

除数函数的定义可以写成

\sigma_k= 1 * Id_k

欧拉函数的性质可以写成

Id=\varphi * 1

Mobius 函数

莫比乌斯函数 \mu(n) 的定义为

\mu(n)= \begin{cases} 1&n=1\\ (-1)^s&n=p_1 p_2 \dots p_s\\ 0&\text{otherwise} \end{cases}

其中 p_1 , p_2 \dots p_s 为不同的质数

容易看出， \mu(n) 在 n 无平方因子时非 0 。

### 非常非常重要的性质 对于任意正整数 $n$ ，有 $\sum\limits_{d|n}\mu(d)=\epsilon (n)

写成狄利克雷卷积的形式即为

\mu * 1=\epsilon

Proof:

若 $n \gt 1$，设 $n$ 有 $s$ 个**不同的**质因子，由于 $\mu(d) \ne 0$ 当且仅当 $d$ **无平方因子**，故 $d$ 中每个素因子的指数只能为 $0$ 或 $1$。故有 $\sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^{s}(-1)^i \dbinom{s}{i}=\sum\limits_{i=0}^{s}1^{s-i}(-1)^i \dbinom{s}{i}=(1-1)^s=0

（第三步使用了 二项式定理 ）

Mobius 变换

我们有数论函数 f ，定义数论函数 g 。若

g(n)=\sum\limits_{d|n}f(d)

则称 g 为 f 的 Mobius 变换 ，f 为 g 的Mobius 逆变换。

写成 Dirichlet 卷积 的形式即为 g=f * 1

Mobius 反演定理

Mobius 反演定理 指出，上式的充要条件为

f(n)=\sum\limits_{d|n}g(d)\mu(\frac{n}{d})

写成 Dirichlet 卷积 形式即为 f=g*\mu

Proof:

把 \mu 的定义代进去就证出来了（

可是我们有更优美的证明方法

f = f * \epsilon = f * 1 * \mu = g * \mu

关于解题

首先我们来看一道题。

求二元组 (x,y) 的个数，满足 1\le x\le n, 1\le y \le m 且 x,y 互质

显然，答案为

\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j)=1]

进行转化

\begin{aligned} \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} [\gcd(i,j)=1] &= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \epsilon(\gcd(i,j))\\ &= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|\gcd(i,j)} \mu(d)\\ &= \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} \sum\limits_{d|i,d|j} \mu(d)\\ &= \sum\limits_{d=1}^{n} \mu(d) \left\lfloor \frac{n}{d} \right\rfloor \left\lfloor \frac{m}{d} \right\rfloor \end{aligned}

（第二步使用了 Mobius 函数的性质 \mu * 1 = \epsilon）

然后这个式子可以通过预处理 \mu ，然后数论分块在 \mathcal{O(\sqrt n)} 时间内求出

​