欧拉函数

文章转载自算法学习笔记(18): 欧拉函数 - 知乎 (zhihu.com)，如有侵权，请联系作者删除。

---

欧拉函数的引入及性质

欧拉函数\(\varphi(x)\)是一个非常重要的函数，它定义为小于（或不大于，这里是一样的）\(x\)但与\(x\)互质的正整数的数量，例如\(\varphi (12)=4\)，有1、5、7、11与之互质。特别地，规定\(\varphi (1)=1\)。

主要性质如下：

若\(p\)是质数，则\(\varphi (p^n)=p^{n-1}(p-1)\)

若\(a|x\)，则\(\varphi (ax)=a\varphi (x)\)

若\(a、b\)互质，则\(\varphi(a)\varphi(b)=\varphi(ab)\)

（这里跳过证明，想要看证明的可以看看原文章：算法学习笔记(18): 欧拉函数 - 知乎 (zhihu.com)）（也许我自己以后会补充？）

注意：符合第三个性质的函数称为积性函数。

---

我们把正整数质因数分解：

\(x={p_1}^{k_1}{p_2}^{k_2}······{p_n}^{k_n}\)。

所有\({p_i}^{k_i}\)两两互质，由欧拉函数的性质得：

\(\varphi (x)={p_1}^{k_1-1}(p_1-1){p_2}^{k_2-1}(p_2-1)······{p_n}^{k_n-1}(p_n-1)\).

即：

\(\varphi (x)=x·\frac{p_1-1}{p_1}·\frac{p_2-1}{p_2}······\frac{p_n-1}{p_n}\)

我们可以利用这个方法以最坏的时间复杂度\(O(\sqrt{n})\)内求出指定正整数的欧拉函数值。

int phi(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            res = res / i * (i - 1); // 先除再乘防止溢出
        while (n % i == 0) // 每个质因数只处理一次，可以把已经找到的质因数除干净
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1); // 最后剩下的部分也是原来的n的质因数
    return res;
}

---

我们还可以把求欧拉函数与筛法结合起来，例如用类似埃氏筛的方法，求1~n的欧拉函数：

int phi[MAXN];
void init(int n)
{
    for (int i = 1; i <= n; i++)
        phi[i] = i; // 除1外没有数的欧拉函数是本身，所以如果phi[i] = i则说明未被筛到
    for (int i = 2; i <= n; i++)
        if (phi[i] == i) // 未被筛到
            for (int j = i; j <= n; j += i) // 所有含有该因子的数都进行一次操作
                phi[j] = phi[j] / i * (i - 1);
}

可以保证范围内每个数都能被它的所有质因数筛且只筛一次。注意一个正整数\(x\)是质数的充要条件是

\(\varphi (x)=x-1\)，所以我们其实顺便求出了所有的素数。这个方法的时间复杂度是\(O(nloglog\ n)\)，比一个一个求的\(O(n\sqrt{n})\)更好。

当然也可以在欧拉筛途中顺便求出：

void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i), phi[i] = i - 1; // 性质一，指数为1的情形
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                phi[p * i] = phi[i] * p; // 性质二
                break;
            }
            else
                phi[p * i] = phi[p] * phi[i]; // 这时肯定互质，用性质三
        }
    }
}

这里没有进行质因数分解，综合运用了开头提到的三种性质，时间复杂度为\(O(n)\) 。