JZTXT

欧拉函数

发布时间 2023-04-07 20:52:04作者: 2huk

欧拉函数 \(\phi\)

定义

\(\phi(n)\) 表示 \(1 \sim n\) 中与 \(n\) 互质的数的个数。

公式

先将 \(n\) 分解质因数，即：

\(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\ \dots p_k^{\alpha_k}\)

则 \(\phi(n) = n \cdot \prod_{i=1}^k (1-\dfrac{1}{p_i})\)。

即 \(\phi(n) = n \cdot \left(1-\dfrac{1}{p_1}\right)\cdot \left(1-\dfrac{1}{p_2}\right)\dots\left(1-\dfrac{1}{p_k}\right)\)

也可以写成 \(\phi(n) = n \cdot \dfrac{p_1-1}{p_1}\cdot \dfrac{p_2-1}{p_2}\dots\dfrac{p_k-1}{p_k}\)

例如：

\(n = 6 = 2^1 \cdot 3^1\)

\(\phi(6) = 6 \cdot \left(1-\dfrac12 \right) \cdot \left(1-\dfrac13 \right) = 2\)

\(\phi(6) = 6 \cdot \dfrac{2-1}2 \cdot \dfrac{3-1}3 = 2\)

依据

容斥原理

推导

  1. 从 \(1 \sim n\) 中去掉 \(p_1,p_2,\dots,p_k\) 的所有倍数，即 \(n \gets n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)。
  2. 加上所有 \(p_i \cdot p_j\) 的倍数，即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)。
  3. 减去所有 \(p_i \cdot p_j \cdot p_k\) 的倍数，即 \(n \gets n-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。
  4. 加上所有 \(p_i \cdot p_j \cdot p_k \cdot p_l\) 的倍数，即 \(p_i \cdot p_j \cdot p_k\) 的倍数，即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。

\[\Large \vdots \]

因此，

$\phi(n) = $

\(n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)

\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)

\(-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)

\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)

\(- \dots\)

也就是 \(n\) 减去奇数个质因子的倍数，加上偶数个质因子的倍数，循环往复。

将上式等价变形，得到刚才提到的公式。

代码

cin >> n;
res = n;	// 初始值为 n 

for(int i=2; i<=n/i; i++){
	// 如果 i 是 n 的质因子 
    if(n%i == 0){
        res = res / i * (i - 1);
    	// 或 res * (1 - 1 / i);
    	// 或 res * ((i - 1) / i);
    	// 但如果使用后面 2 种，则需要考虑实数问题 
        while(n%i == 0){
            n /= i;
        }
    }
}

// 如果还剩下大于根号 n 的质因子，再次统计到答案种 
if(n > 1){
    res = res / n * (n - 1);
}

cout << res;

求多个数欧拉函数之和

求 \(1\) 个数的欧拉函数时间复杂度是 \(\Theta(\sqrt{n})\)，求 \(n\) 个数的时间复杂度即 \(\Theta(n \cdot \sqrt{n})\)，那如何进行优化，使其变成 \(\Theta(n)\) 呢？

可以先线性地筛出 \(n\) 以内的所有质数，在进行求解。

线性筛指数的代码如下:

for(int i=2; i<=n; i++){
    if(!st[i]){
        p[cnt++] = i;
    }
    for(int j=0; p[j] <= n/i; j++){
        st[p[j] * i] = 1;
        if(i%p[j] == 0){
            break;
        }
    }
}

如何对其进行修改呢？

边界条件

从定义出发设置边界条件，即 \(\phi(1) = 1\)。

如果 \(i\) 是质数

如果 \(i\) 是质数，那么在 \(1 \sim n\) 当中 \(1 \sim n-1\) 都是与其互质的数，即 \(\phi(i) = i-1\)。

内层循环

如果 \(p_j\) 是 \(i\) 的最小质因子

因为一个数分解质因数后的指数与欧拉函数结果无关，因此 \(p_j \cdot i\) 和 \(i\) 的质因子是相同的，因为将 \(p_j \cdot i\) 和 \(i\) 分解质因数后，\(p_j \cdot i\) 只会比 \(i\) 的指数多1。

我们假设 \(i\) 的质因子是 \(q_1,q_2,\dots,q_k\)，那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

由于 \(p_j\) 是 \(i\) 的质因子，又因为 \(p_j \cdot i\) 的质因子与 \(i\) 相同，那么，

\(\phi(p_j\cdot i) = p_j \cdot i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同，所以我们可以下结论：

\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \]

如果 \(p_j\) 不是 \(i\) 的最小质因子

那么 \(p_j\) 就是 \(p_j \cdot i\) 的最小质因子，且 \(p_j\) 是不包含在 \(i\) 的质因子当中的。

因此，假设 \(i\) 的所有质因子是 \(q_1, q_2,\dots,q_k\)，那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。

则 \(\phi(p_j \cdot i) = p_j \cdot i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right) \cdot \left(1-\dfrac{1}{p_j}\right)\)。

其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同，所以我们可以下结论：

\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \cdot \left( 1-\dfrac{1}{p_j}\right) = \phi(i) \cdot (p_j - 1) \]

代码

int get_phi(int n){
    phi[1] = 1;     // 特殊规定
    for(int i=2; i<=n; i++){
        if(!st[i]){
            p[cnt++] = i;
            phi[i] = i - 1;     // 如果 i 是质数，它的欧拉函数是 i-1
        }
        for(int j=0; p[j] <= n/i; j++){
            st[p[j]*i] = 1;     // p[j] * i 不是质数
            if(i % p[j] == 0){  // p[j] 是 i 的最小质因子
                phi[p[j] * i] = phi[i] * p[j];
                break;
            }
            else{   // p[j] 是 p[j] * i 的最小质因子
                phi[p[j] * i] = phi[i] * (p[j] - 1);
            }
        }
    }
    int res = 0;
    // 统计所有数的欧拉函数之和
    for(int i=1; i<=n; i++){
        res += phi[i];
    }
    // 返回
    return res;
}

欧拉定理

若 \(a\) 与 \(n\) 互质，则有 \(a^{\phi(n)} \equiv 1 (\bmod\ n)\)。