数论 —— 欧拉函数

数论算法，欧拉函数公式推导 + 代码

华幽子丶

3414人浏览 · 2023-01-30 21:41:16

华幽子丶 · 2023-01-30 21:41:16 发布

欧拉函数

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

公式

$N(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})....(1- \dfrac{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$ 在 $[1, N]$ 内的倍数的个数为 $Np1\dfrac{N}{p_1}$

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

…

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

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

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

$p_1p_2$ 在 $[1, N]$ 内的倍数的个数为 $Np1p2\dfrac{N}{p_1p_2}$

$p_1p_3$ 在 $[1, N]$ 内的倍数的个数为 $Np1p3\dfrac{N}{p_1p_3}$

$p_2p_3$ 在 $[1, N]$ 内的倍数的个数为 $Np2p3\dfrac{N}{p_2p_3}$

…

所以将他们加回去，即 $\dfrac{N}{p_1}-\dfrac{N}{p_2}.....-\dfrac{N}{p_k}+\dfrac{N}{p_1p_2}+\dfrac{N}{p_1p_3}+\dfrac{N}{p_2p_3}....$

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

$p_1p_2p_3$ 在 $[1, N]$ 内的倍数的个数为 $Np1p2p3\dfrac{N}{p_1p_2p_3}$ ，则

$KaTeX parse error: \tag works only in display equations$

而这条式子化简之后就是欧拉函数公式
$N(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})(1-\dfrac{1}{p_3})...(1-\dfrac{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$ 是质数的时， $e u l er (i) = i - 1$

$(2) (3)$ 式：

当一个数是合数的时候，它在第二个for循环中被筛掉。
但合数的欧拉函数会出现两种情况：
- 当 $i$ 能被 $p r im es [j]$ 整除时
  - 说明 $p r im es [j]$ 是 $i$ 的一个质因子（且是最小质因子），则 $i$ 的所有质因数为 ${ p_1,p_2,...p_k,p_j\}$ （我们将 $p r im es [j]$ 记作 $p_j$ ）。而合数 $i×primes[j]i\times primes[j]$ （我们将 $p r im es [j]$ 记作 $p_j$ ）的所有质因数也是 ${ p_1,p_2,...p_k,p_j\}$ ，则
  - $euler(i\times p_j) =ip_j(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_j})\\ euler(i)=i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_j})$
  则:
  - $euler(i\times p_j) = euler(i)\times p_j$
  - 而就是 $(2)$ 式
- 当 $i$ 不能被 $p r im es [j]$ 整除时
  - 则 $i$ 的质因数没有 $p_j$ ，是 ${p_1,p_2...p_k \}$ ，则此时
  - $i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k})$
  - 而 $i×pji\times p_j$ 的质因数为 ${p_1,p_2...p_k,p_j \}$ ，则
  - $\times p_j) = ip_j(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k})(1-\dfrac{1}{p_j})$
    
    式子整理后
  - $\times p_j) = i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k})(p_j-1)$
  - 将两式子结合为
    $\times p_j) =euler(i)\times (p_j - 1)$
  - 即为 $(3)$ 式