欧拉函数

​ 定义一个函数 $euler(N)$ 为 $[1,N]$ 中与 $N$ 互质的数的个数，这个函数称为 欧拉函数

公式

$$euler(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})....(1-\frac{1}{p_k})$$

​ $p_i$ 为 $N$ 的所有质因数

性质

• 欧拉函数的值与 $N$ 的质因子的指数无关

推导

• 基于容斥原理推导

思路

​ 欧拉函数求的是 $[1,N]$ 中与 $N$ 互质的数的个数，我们反过来看 $[1,N]$ 中有几个数与 $N$ 不互质；与 $N$ 不互质，说明与 $N$ 有一些公共质因数，所以我们将 $N$ 的所有质因数的倍数的个数减去，剩下的就是互质数的个数

假设 $N$ 的质因数为 { p 1 , p 2 , p 3 . . . . , p k } \{ p_1,p_2,p_3....,p_k\} {p1​,p2​,p3​....,pk​}， 则

$p_1$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_1}$

$p_2$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_2}$

…

$p_k$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_k}$

所以我们将他们减去，即 $N-\frac{N}{p_1}-\frac{N}{p_2}.....-\frac{N}{p_k}$

但是，有些数会是多个质因数的公倍数，他们被重复减了，所以要把他们加回去

$p_1{p}_2$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_1{p}_2}$

$p_1{p}_3$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_1{p}_3}$

$p_2{p}_3$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_2{p}_3}$

…

所以将他们加回去，即 $N-\frac{N}{p_1}-\frac{N}{p_2}.....-\frac{N}{p_k}+\frac{N}{p_1{p}_2}+\frac{N}{p_1{p}_3}+\frac{N}{p_2{p}_3}....$

但是但是，我们又发现，如果一个数同时是 $p_1{p}_2{p}_3$ 的公倍数，那么经过最上面被减了三次，然后又被加了三次，相当于没减，所以我们还要将他减掉

$p_1{p}_2{p}_3$ 在 $[1,N]$ 内的倍数的个数为 $\frac{N}{p_1{p}_2{p}_3}$，则

KaTeX parse error: \tag works only in display equations

而这条式子化简之后就是欧拉函数公式
$$euler(N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})...(1-\frac{1}{p_k})$$
得证

代码

定义法

• 思路：一边分解质因数，一边求欧拉函数
• 但是一次只能求一个数的欧拉函数

int get_euler(int n)
{
    int euler = n;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            euler = euler / i * (i - 1) //euler = euler * (1 - 1 / i); 
            while (n % i == 0) n /= i;
        }
    }
    
    if (n > 1) euler = euler / n * (n - 1);
    return euler;
}

线性筛法

• 在线性筛筛质数的过程中，求出每个数的欧拉函数
• 可以一次筛的过程中一次性将 $[1,N]$ 中所有数的欧拉函数都求出来，但是思路需要推导

int primes[N], cnt = 0;
int euler[N];
bool st[N];

int get_euler(int n)
{
	euler[1] = 1; // 1的欧拉函数值是1
    
    // 线性筛模板 + 过程中求欧拉函数
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt ++] = i;
            euler[i] = i - 1; // (1)式
        }
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[i *primes[j]] = true;  
            if (i % primes[j] == 0)
            {
                euler[i * primes[j]] = euler[i] * primes[j]; //(2)式
                break;
            }
             euler[i * primes[j]] = euler[i] * (primes[j] - 1);//(3)式
        }
    }
    // 最后，euler数组中存的就是 1 ~ n 每个数的欧拉函数值 
}

$(1)(2)(3)$ 式的推导

$(1)$ 式：

• 当 $i$ 是质数的时候，质数的因数只有 $1$ 和他本身，所以 $i$ 会与小于它的所有数互质，即 $i$ 与 $[1,i-1]$ 中所有数互质。即：当 $i$ 是质数的时， $euler(i)=i-1$

$(2)(3)$ 式：

• 当一个数是合数的时候，它在第二个for循环中被筛掉。

• 但合数的欧拉函数会出现两种情况：

  • 当 $i$ 能被 $primes[j]$ 整除时

    • 说明 $primes[j]$ 是 $i$ 的一个质因子（且是最小质因子），则 $i$ 的所有质因数为 { p 1 , p 2 , . . . p k , p j } \{ p_1,p_2,...p_k,p_j\} {p1​,p2​,...pk​,pj​}（我们将 $primes[j]$ 记作 $p_j$）。而合数 $i\times primes[j]$ （我们将 $primes[j]$ 记作 $p_j$） 的所有质因数也是 { p 1 , p 2 , . . . p k , p j } \{ p_1,p_2,...p_k,p_j\} {p1​,p2​,...pk​,pj​}，则

    • $$\begin{gathered} euler(i\times p_j)=i{p}_j(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_j}) \\ euler(i)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_j}) \end{gathered}$$

    则:

    • $$euler(i\times p_j)=euler(i)\times p_j$$

    • 而就是 $(2)$ 式

  • 当 $i$ 不能被 $primes[j]$ 整除时

    • 则 $i$ 的质因数没有 $p_j$，是 { p 1 , p 2 . . . p k } \{p_1,p_2...p_k \} {p1​,p2​...pk​}，则此时

    • $$euler(i)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$$

    • 而 $i\times p_j$ 的质因数为 { p 1 , p 2 . . . p k , p j } \{p_1,p_2...p_k,p_j \} {p1​,p2​...pk​,pj​}，则

    • $$euler(i\times p_j)=i{p}_j(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})(1-\frac{1}{p_j})$$

      式子整理后

    • $$euler(i\times p_j)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})(p_j-1)$$

    • 将两式子结合为
      $$euler(i\times p_j)=euler(i)\times (p_j-1)$$

    • 即为$(3)$ 式