欧拉函数

定义

一个数 $x$ 的欧拉函数 $\varphi(x)$ 为小于 $x$ 的正整数中与 $x$ 互质的数的个数。

特别地，$\varphi(1)=1$。

求法

1. $\varphi(n)=n\textstyle\prod^n_{i=1}(1-\frac{1}{p_i})$，其中 $p_i$ 是 $n$ 的所有质因数。
2. 线性筛求欧拉函数值。

性质

1. 是积性函数。
2. 对质数 $p$ ，$\varphi(p)=p-1$。
3. 小于 $n$ 的数中，与 $n$ 互质的数之和为 $\varphi(n)\times\dfrac{n}{2}(n \lt 1)$。
4. $n$ 的所有因数的欧拉函数之和等于 $n$ ，即 $n=\textstyle\sum_{d\mid n}\varphi(d)$。

线性筛求欧拉函数

• 在线性筛中，每一个合数都被最小的质因子筛掉。

  设 $p_1$ 是 $n$ 的最小质因子， $n’=\dfrac{n}{p_1}$ ，那么线性筛时 $n$ 通过 $x’\times p_1$ 筛掉。

• 如果 $n’ \bmod p_1=0$ ，那么 $n’$ 包含了 $n$ 的所有质因子。

  $\begin{aligned}\varphi(n)&=n\times \displaystyle\prod^s{i=1}\dfrac{p_i-1}{p_i}\&=p_i\times n’\times\displaystyle\prod{i=1}^{s}\dfrac{p_i-1}{p_i}\&=p_1\times \varphi(n’)\end{aligned}$

• 如果 $n’ \bmod p_1 \not=0$ ，此时 $n’$ 与 $p_1$ 互质，因为欧拉函数是积性函数，则

  $\varphi(n)=\varphi(p_1)\times\varphi(n’)=(p_1-1)\times\varphi(n’)$

• int vis[maxN];
  int p[maxN];
  int phi[maxN];
  int pn;
  
  inline void getPhi(int N) {
      for (int i = 2; i <= N; i++) {
          if (!vis[i]) {
              p[++pn] = i;
              phi[i] = i - 1;
          }
          for (int j = 1; i * p[j] <= N; j++) {
              vis[i * p[j]] = 1;
              if (i % p[j] == 0) {
                  phi[i * p[j]] = phi[i] * p[j];
                  break;
              }
              phi[i * p[j]] = phi[i] * phi[p[j]];
          }
      }
  }
  

欧拉定理

若 $\gcd(a,m)=1$，则 $a^{\varphi(m)}\equiv1 \pmod m$

扩展欧拉定理

$a^b\equiv \begin{cases}a^{b \bmod \varphi(p)}, & \gcd(a,p)=1\a^b, &\gcd(a,p)\not=1,b\lt\varphi(p)\a^{b \bmod \varphi(p)+\varphi(p)},&\gcd(a,p)\not=1,b\geq\varphi(p)\end{cases}\pmod p$