「算法笔记」欧拉函数

欧拉函数是数论中的一个重要积性函数。


定义

欧拉函数 $\varphi(n)$ 表示 $[1,n]$ 中与 $n$ 互质的正整数的个数。例如,$\varphi(p)=p-1,\varphi(1)=1$。


计算式

首先我们证明如下公式(其中 $p$ 为质数):

$$ \varphi(p^c)=p^c-p^{c-1} $$

这个公式计算的证明十分简单,我们考虑容斥原理。$[1,p^c]$ 中与 $p^c$ 不互质的数的个数有 $\frac{p^c}{p}$ 个,即 $p^{c-1}$ 个,证明完毕。

有了这个式子,在加上欧拉函数是积性函数,我们可以得到计算式:

$$ \text{设}\ n\ \text{的质因子分解式为}\ \prod_{i=1}^k {p_i}^{c_i}\text{,则}\ \varphi(n)=n\prod_{i=1}^k\frac{p_i-1}{p_i} $$


性质

欧拉函数有一个重要的性质:

$$ n=\sum_{d\mid n}\varphi(d)\Longleftrightarrow \varphi\ast 1=\operatorname{ID} $$

这个证明过程在「算法笔记」莫比乌斯反演 中已经涉及,我们在此再次证明一遍:

$$ \begin{aligned} \varphi\ast 1 & =\sum_{d\mid n}\varphi(\frac{n}{d}) \\ & =\sum_{i=0}^c\varphi(p^i) \\ & =1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1) \\ & =p^c \\ & =\operatorname{ID} \\ \end{aligned} $$


求值

线性筛

由于欧拉函数是积性函数,所以可以线性筛,代码如下:

void sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            p[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            } else {
                phi[i * p[j]] = phi[i] * phi[p[j]];
            }
        }
    }
}

单个求值

此时我们只要按照定义来做就行啦!(把质数预处理出来可以加速)

int phi(int x) {
    int ans = x;
    for (int i = 1; i <= tot && p[i] * p[i] <= x; i++) {
        if (x % p[i]) continue;
        ans = ans / p[i] * (p[i] - 1);
        while (x % p[i] == 0) x /= p[i];
    }
    if (x > 1) ans = ans / x * (x - 1);
    return ans;
}

欧拉定理

当我们要求 $a^b\bmod p$ 时,显然指数不能直接对 $p​$ 取模,为此我们引入欧拉定理。

  • 欧拉定理:若 $\gcd(a,p)=1$,则 $a^{\varphi(p)}\equiv 1\pmod p$。
  • 扩展欧拉定理:若 $b > \varphi(p)$,则 $a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p​$。此处不需要 $p$ 为质数的条件!

因此我们可以得到如下公式:

$$ a^c=\begin{cases} a^{b\bmod\varphi(p)} & \gcd(a,p)=1 \\ a^b & \gcd(a,p)\neq 1,c<\varphi(p) \\ a^{b\bmod\varphi(p)+\varphi(p)} & \gcd(a,p)\neq 1,c\ge\varphi(p) \end{cases} $$

证明的话用同余和完全剩余系之类的就行了?


习题

发表评论