欧拉函数

欧拉函数的定义：$1\sim n$ 中与 $n$ 互质的数的个数被称为 $n$ 的欧拉函数，记为 $\varphi (n)$。例如 $\varphi (6)=2$。

根据算术基本定理，$n$ 可以写成所有质因数的乘积：

$$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_m^{{\alpha }_m},$$

欧拉函数的性质：

• $\varphi (1)=1$
• 如果 $p$ 是质数，那么 $\varphi (p)=p-1$
• 如果 $n=p^k$ 是质数的次方，那么 $\varphi (n)=p^k-p^{k-1}$
  • 这是因为和 $n$ 互质的数一定不是 $p$ 的倍数
  • 而 $p$ 的倍数有 $p,2p,\cdots ,p^{k-1}\times p$ 共计 $p^{k-1}$ 个
• 如果 $n$ 可以分解为两个互质整数乘积，那么 $\varphi (n)=\varphi (pq)=\varphi (p)\varphi (q)$
  • 注意这里的两个整数是互质的，不一定是质数
  • TODO：中国剩余定理证明

欧拉函数的计算：

$$\varphi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$$

证明：容斥原理：

• 从 $1\sim n$ 中去掉所有 $p_1,p_2,\cdots ,p_k$ 的倍数
• 上一步删除了很多重复元素，这一步加上 $p_1{p}_2,p_1{p}_3,\cdots ,p_{k-1}{p}_k$ 的倍数
• 循环往复……

$$\begin{array}{rl}\varphi (n)& =n-\frac{n}{p_1}-\frac{n}{p_2}-\cdots -\frac{n}{p_k}+\frac{n}{p_1{p}_2}+\cdots \\ & =n-n\sum _{i=1}^k\frac{1}{p_i}+n\sum _{i\ne j}^k\frac{1}{p_i{p}_j}-\cdots \\ & =n(1+\sum _{i=1}^n\sum _{1\le j_1<j_2<\cdots <j_i\le n}(-1{)}^i\frac{1}{p_{j_1}{p}_{j_2}{p}_{j_3}\dots p_{j_i}})\end{array}$$

我们可以看到系数只有正负一两种，而偶数个质因子作为分母都是 -1，奇数个质因子作为分母则是 +1，二者一致，因此公式是正确的。

算法的时间复杂度瓶颈在于对 $n$ 分解质因数，得到质因数后 $O(1)$ 就可以算出来。

AC873. 欧拉函数

线性筛求欧拉函数

给定一个正整数 $n$，可以在 $O(n)$ 的时间内求出 $1\sim n$ 的欧拉函数（注意上一个是用 $O(\sqrt{n})$ 时间求出了正整数 $n$ 的欧拉函数）

AC874. 筛法求欧拉函数

这里注意一个细节：$6$ 和 $2^{10}\times 3^{20}$ 除去 $n$ 后面两个括号里的东西是一样的都是 $1/3$。

核心代码：

void get_euler(int n) {
    phi[1] = 1;

    for (int i = 2; i <= n; i ++) {
        if (!st[i]) {
            primes[cnt ++] = i;

            phi[i] = i - 1;
        }

        for (int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;

            if (i % primes[j] == 0) {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            else {
                phi[primes[j] * i] = phi[i] * (primes[j] - 1); 
            }
        }
    }
}

在 if (i % primes[j] == 0) 没有判定 break 之前，进入该循环的数都是刚用最小质因子筛掉的合数。具体可以参见 31-质数 中的线性筛一节。

• phi[primes[j] * i] = phi[i] * primes[j];：公式
• phi[primes[j] * i] = phi[i] * (primes[j] - 1); ：积性

欧拉定理

设 $a,n\in {\mathbb{N}}^{\ast }$，且二者互质，则有：

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

证明：对于 $1\sim n$ 中，有 $\varphi (n)$ 个和 $n$ 互素的数，记为：

$$a_1,a_2,\cdots ,a_{\varphi (n)}$$

可以证明，$a{a}_i$ 也是（模 $n$ 意义下）互不相同的 $\varphi (n)$ 个数。这里用到反证法，假设 $a{a}_i\equiv a{a}_j(\mathrm{mod}n)$，那么 $a(a_i-a_j)\equiv 0(\mathrm{mod}n)$。由于 $a,n$ 互质，因此有 $a_i\equiv a_j(\mathrm{mod}n)$，这里由于 $a_i<n,a_j<n$，因此得出 $a_i=a_j$，矛盾。

而由于 $a{a}_i$ 与 $n$ 互质，因此所有的 $a{a}_i$ 构成了模 $n$ 的 简化剩余系，是完全剩余系中与 $n$ 互素的数构成的子集。显然，$a_1,a_2,\cdots ,a_{\varphi (n)}$ 正是模 $n$ 的简化剩余系。因此：

$$a^{\varphi (n)}(a_1{a}_2\cdots a_{\varphi (n)})\equiv a_1{a}_2\cdots a_{\varphi (n)}(\mathrm{mod}n)$$

由于 $a_1{a}_2\cdots a_{\varphi (n)}$ 和 $n$ 互质，因此：

$$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$

得证。