「算法笔记」欧拉函数

发表于 | | 阅读次数:
字数统计: 594 字
欧拉函数是数论中的一个重要积性函数。

定义

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

计算式

首先我们证明如下公式（其中 $p$ 为质数）：

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

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

性质

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

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

求值

线性筛

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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]]=1;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            } else {
                phi[i*p[j]]=phi[i]*phi[p[j]];
            }
        }
    }
}

单个求值

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

1
2
3
4
5
6
7
8
9
10
 
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​$。

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

证明的话用同余和完全剩余系之类的就行了？（大雾

习题

0%