# 欧拉函数

欧拉函数：数字 1~n 中与 n 互质 的数的 个数 ，记为$\varphi(n)$。

互质的数：公约数只有 1 的两个数。

例如：$\varphi(12)=4$，其中 1~12 中共有 4 个与 12 互质的数，分别是 1，5，7，11 。

# 如何求欧拉函数？

# 一个重要性质

这里我们依赖欧拉函数的一个重要性质欧拉函数是一个积性函数，也就是当 n 与 m 互质时，公式$\varphi(nm)=\varphi(n)*\varphi(m)$ 成立。

# 求解方案

1. 首先，对 n 进行质因数分解。
   记为如下公式：$n={p_1}^{a_1} * {p_2}^{a_2} * ... * {p_k}^{a_k}$。

   其中每一项都与其他项互质，根据积性函数的性质，上面公式还可以写成：$\varphi(n)=\varphi({p_1}^{a_1}) * \varphi({p_2}^{a_2}) * ... * \varphi({p_k}^{a_k})$ 。

   例如：$12=2^2*3$，那么$\varphi(12)=\varphi(2^2)*\varphi(3)$

2. 此时，问题转换为求$\varphi({p_k}^{a_k})$。

   1. 1~${p_k}^{a_k}$ 的中共有${p_k}^{a_k}$ 个数字，因为${p_k}$ 是 质数 ，所以与${p_k}^{a_k}$ 不互质 的数就是${p_k}$ 的倍数 (因为他们的公约数除了 1 之外，一定还有${p_k}$ 本身)，也就是${p_k}， 2{p_k}， 3{p_k}，...{p_k}^{a_{k-1}}*p_k$，总共有${p_k}^{a_{k-1}}$ 个。
      例如：pk=3,ak=5，此时共有 (2*3,3*3,4*3, ... ,3^4 * 3) 是与 3 不互质的数。

   2. 所以，用总数${p_k}^{a_k}$ 去掉其中非互质的个数${p_k}^{a_{k-1}}$，剩下的就是与${p_k}^{a_k}$ 互质的。也就是 $\varphi (p_k}({a_k))=p_k}({a_k)-p_k}({a_{k-1)}=p_k}({a_k)*(1-\frac{1}{p_k}) $。

3. 最后，我们整理一下公式：

   $\varphi(n)=\varphi({p_1}^{a_1}) * \varphi({p_2}^{a_2}) * ... * \varphi({p_k}^{a_k})$

   $=\varphi({p_1}^{a_1}) * \varphi({p_2}^{a_2}) * ... * \varphi({p_k}^{a_k})$

   $=({p_1}^{a_1} * (1-\frac{1}{p_1})) *({p_2}^{a_2} * (1-\frac{1}{p_2})) * ... *({p_k}^{a_k} * (1-\frac{1}{p_k}))$

   $={p_1}^{a_1}*{p_2}^{a_2}*...* {p_k}^{a_k} * (1-\frac{1}{p_1}) * (1-\frac{1}{p_2})*...*(1-\frac{1}{p_k})$

   $=n*(1-\frac{1}{p_1}) * (1-\frac{1}{p_2})*...*(1-\frac{1}{p_k})$

   $=n*\prod_{k}^{i=1}(1-\frac{1}{p_i} )$

# Code

注意，在公式中存在$(1-\frac{1}{p_k})$，这种情况如果直接计算，要计算小数，也就是$\frac{1}{p_k}$ 这里，因此，我们把这里进行一下等价变换：$n*(1-\frac{1}{p_i})\Rightarrow n{\div} p_i * (p_i - 1)$ 。

def find(n):

    i = 2

    res = n

    # 分解质因数

    while i <= n // i:

        if n % i == 0:

            while n % i == 0:

                n //= i

            # 根据分析的公式计算个数。

            res = res // i * (i - 1)

        i += 1

    if n > 1:

        res = res // n * (n - 1)

    return res

# 筛法求欧拉函数

问题升级：要求出 1~n 中所有数字的欧拉函数。

此时，我们发现如果还用上面的方法求 1~n 中每个数字的欧拉函数，那么每个数都要分解质因数，时间复杂度会来到$O(n\sqrt{n})$ 。

那么，回想一下在上一篇文章中，我们 求1~n中的质数 时候是怎么做的呢？

我们使用了一个线性筛法，在$O(n)$ 的时间复杂度下就求出来了 1~n 中的质数。

而在求欧拉函数的时候，我们也要分解质因数，因此可以在求解质数的时候顺便把欧拉函数也求出来。

首先复习一下，质数的线性筛是怎么做的。

def get_primes(n):

    cnt = 0

    for i in range(2, n + 1):

        if not st[i]:  # 判断是否是质数

            p[cnt] = i # p 存放质数

            cnt += 1

        # 循环 2

        j = 0

        while p[j] <= n // i:

            st[p[j] * i] = 1

            # 结束条件

            if i % p[j] == 0:

                break

            j += 1

    return cnt

从代码中可以比较容易的分析到，筛选过程总共分为两部分，一部分是质数部分，另一部分是筛掉的合数部分。

# 质数部分

在质数部分，求质数的欧拉函数是非常简单的。从定义出发很容易想到 质数n 的欧拉函数就是$\varphi(n)=n-1$。

因为 质数的因数只有1和它本身 ，而欧拉函数的定义是 1~n中与n互质的个数 ，那么除了 n 之外，1~n-1 中所有数都与 n 只有 1 这一个共同因数，所以它们都与 n 互质，总个数就是 n-1 个。

用上小节的求欧拉函数的公式表示就是：$\varphi(n)=n*(1-\frac{1}{n})=n-1$ 。

# 合数部分

1. 当触发中止条件 i % p[j] == 0 时，说明 pj 是 i 的质因子。

   从上节欧拉函数的推导过程中，我们发现一个数的欧拉函数计算过程和其质因子的指数是没关系的，只与质因子本身有关。

   例如：当 n=6 时候，分解质因数结果是$2*3$，那么求欧拉值：$\varphi(6)=6*(1-\frac{1}{2})*(1-\frac{1}{3})=2$。
   当 n=12 时候，分解质因数结果是$2^2*3$，因此，它求欧拉值是$\varphi(12)=12*(1-\frac{1}{2})*(1-\frac{1}{3})=4$。

   举这个例子，是想说明上面的结论。即，求欧拉值的过程中， 6 和 12 都有相同的质因数 2 和 3 。虽然 12 的 质因子2 的指数是 2 ，而 6 的 质因子2 的指数是 1 ，但这并没有影响$(1-\frac{1}{2})*(1-\frac{1}{3})$ 这部分。

   所以，当$\varphi(i*p_j)$ 中，如果$p_j$ 是 i 的质因子之一，那么$\varphi(p_j)=p_j * (1-\frac{1}{p_j})$ 中的$(1-\frac{1}{p_j})$ 已经在$\varphi(i)$ 的推导过程中被计算过了，所以，我们得到最终公式：$\varphi(i*p_j)=p_j *i *(1-\frac{1}{p_1}) *...*(1-\frac{1}{p_j}) *...*(1-\frac{1}{p_k})=p_j * \varphi(i)$。

2. 当不满足终止条件，也就是 i % pj != 0 ，此时$p_j$ 和 i 是互质的，那么根据积性函数的性质，可以得到$\varphi(p_j*i)=\varphi(p_j)*\varphi(i)$。 因为$p_j$ 是质数，所以$\varphi(p_j)=p_j-1$。最后，得到最终公式：$\varphi(p_j*i)=(p_j-1)*\varphi(i)$。

# Code

N = 1000010 # 数据范围

st = [0] * N  # 判断是否是质数

p = [0] * N  # 质数数组

def find(n):

    phi = [0] * N  # 欧拉值数组

    cnt = 0

    for i in range(2, n + 1):

        if not st[i]:

            p[cnt] = i

            phi[i] = i - 1 # 质数的欧拉值

            cnt += 1

        j = 0

        while p[j] <= n // i:

            t = i * p[j]

            st[t] = 1

            if i % p[j] == 0:

                phi[t] = phi[i] * p[j] # pj 是 i 的质因子

                break

            phi[t] = phi[i] * (p[j] - 1)  # pj 不是 i 的质因子

            j += 1

    res = 0

    # 注意这里，因为分解质因式是从 2 开始的

    # 而欧拉值求的是 1~n，必须初始化一下 phi [1] 的值

    phi[1] = 1 

    for i in range(1, n + 1):

        res += phi[i]

    return res