JZTXT

欧拉函数

发布时间 2023-06-06 08:56:55作者: 9981day

欧拉函数

定义

设\(n\)是一个正整数，欧拉函数\(\phi(n)\)定义为不超过\(n\)且与\(n\)互质的正整数的个数

定理1

设\(p\)和\(q\)是互质的正整数，那么

\[\phi(pq) = \phi(p)\phi(q) \]

这个定理说明欧拉函数是一个积性函数，有以下推理

若\(n = p_1^{a_1} * p_2^{a_2} * p_3^{a_3} * ... * p_k^{a_k}\)，其中\(p_1,p_2,p_3...,p_k\)互质，\(a_1,a_2,a_3,...,a_k\)是她们的幂，则\(\phi(n) = \phi(p_1^{a_1}) * \phi(p_2^{a_2}) * \phi(p_3^{a_3}) * ... * \phi(p_k^{a_k})\)

关于欧拉函数是一个积性函数的证明，读者可以感性理解一下，在这里不给出证明

定理2

设\(n\)为正整数，那么

\[n = \sum\limits_{d|n} \phi(d) \]

其中，\(d|n\)表示\(d\)整除\(n\)，上式表示对\(n\)的正因数的欧拉函数求和。

这个定理说明了\(n\)与\(\phi(n)\)的关系:\(n\)的正因数(包括1和\(n\)自身)的欧拉函数之和等于\(n\)

证明

\(n\)个分数\(\frac{1}{n},\frac{2}{n},\frac{3}{n},...,\frac{n}{n}\)互不相等。化简这些分数，得到新的\(n\)个分数，她们的分母和分子互质，形如\(\frac{a}{d}\)，\(d|n\)且\(a\)与\(d\)互质。在所有\(n\)个分数中，分母为\(d\)的分数的数量为\(\phi(d)\)。所有不同分母的分数，其总数为\(\sum\limits_{d|n}\phi(d)\)，所以\(n = \sum\limits_{d|n} \phi(d)\)，得证。

定理3

设\(n = p_1 ^ {a_1} * p_2 ^ {a_2} * p_3 ^ {a_3} * ... * p_k ^ {a_k}\)为正整数\(n\)的质幂因数分解，那么

\[\phi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_3})...(1 - \frac{1}{p_k}) = n \prod\limits_{i = 1} ^ k (1 - p_i) \]

证明

首先，上述公式有以下两种特殊情况

(1)若\(n\)是质数，\(\phi(n) = n - 1\)。

这一点很容易推理，质数的因数只有\(1\)和她本身。

(2)若\(n = p ^ k\)，\(p\)是质数，有\(\phi(n) = \phi(p ^ k) = p ^ k - p ^ {k - 1} = p ^ {k - 1}(p - 1) = p ^ {k - 1} \phi(p)\)。

这一点，我们考虑与\(n\)不互质的数，即因子中含有\(p\)的数，从\(1\)到\(n\)中因子能够含有\(p\)的数有\(p ^ {k - 1}\)个，总共有\(p ^ k\)个数，用总数减掉不互质的数即为欧拉函数。

那么我们如何证明定理3呢

\[\begin{aligned} \phi(n) & = \phi(p_1 ^ {a_1} * p_2 ^ {a_2} * p_3 ^ {a_3} * ... * p_k ^ {a_k}) \\ & = \phi(p_1 ^ {a_1}) \phi(p_2 ^ {a_2}) \phi(p_3 ^ {a_3}) ... \phi(p_k ^ {a_k}) \\ & = (p_1 ^ {a_1} - p_1 ^ {a_1 - 1})(p_2 ^ {a_2} - p_2 ^ {a_2 - 2})(p_3 ^ {a_3} - p_3 ^ {a_3 - 3})...(p_k ^ {a_k} - p_k ^ {a_k - k}) \\ & = p_1^{a_1}(1 - \frac{1}{p_1})p_2^{a_2}(2 - \frac{2}{p_2})p_3^{a_3}(3 - \frac{3}{p_3})...p_k^{a_k}(1 - \frac{k}{p_k}) \\ & = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_3})...(1 - \frac{1}{p_k}) \\ & = n \prod\limits_{i = 1} ^ k (1 - p_i) \end{aligned} \]

欧拉定理

设\(m\)是一个正整数，\(a\)是一个整数且\(a\)与\(m\)互质，即\(gcd(a,m) = 1\)，则有\(a^{\phi(m)} \equiv 1 \pmod m\)。

求单个欧拉函数

有了定理3我们就很容易求出单个欧拉函数了，只需要先用试除法分解质因数，再用公式\(\phi(n) = n \prod\limits_{i = 1} ^ k (1 - p_i)\)求得\(\phi(n)\)。时间复杂度为\(O(\sqrt{n})\)

代码

int phi(int n)
{
    int ans = n;
    for (int i = 2;i * i <= n;i ++)
    {
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);//求欧拉函数通式
            while(n % i == 0) n /= i;//把这个因数的幂去掉
        }
    }
    if (n != 1) ans = ans / n * (n - 1);//n是质数，n = n - 1
    return ans;
}

线性筛求\(1-n\)内的欧拉函数

现在要求\(1-n\)内的所有欧拉函数，前面求单个欧拉函数的复杂度为\(O(\sqrt n)\)，如果一个一个求\(1-n\)内所有欧拉函数，那么总复杂度为\(O(n\sqrt n)\)，效率太低。

注意到在线性筛的过程中，每一个合数都是被她最小的质因数筛掉。比如设\(p_1\)是\(n\)的最小质因数，\(n' = \frac{n}{p_1}\)，那么线性筛的过程中，\(n\)通过\(n' * p_1\)筛掉。

观察线性筛的过程，我们对\(n' \bmod p_1\)分类讨论

如果\(n' \bmod p_1 = 0\)，那么\(n'\)包含了\(n\)的所有质因子。

\[\begin{aligned} \phi(n) & = n * \prod\limits_{i = 1} ^ k (1 - p_i) \\ & = p_1 * n' * \prod\limits_{i = 1} ^ k (1 - p_i) \\ & = p_1 * \phi(n') \end{aligned} \]

如果\(n' \bmod p_1 \ne 0\)，此时\(n'\)与\(p_1\)互质，根据欧拉函数是积性函数可得

\[\begin{aligned} \phi(n) & = \phi(p_1) * \phi(n') \\ & = (p_1 - 1) * \phi(n') \end{aligned} \]

代码

void get_phi()//phi[i]用来储存欧拉函数,vis[i]用来储存最小的质因数,pri[i]用来储存质数
{
    phi[1] = 1;//1的欧拉函数是1
    for (int i = 2;i <= n;i ++)
    {
        if (!vis[i])//没有被筛过，i是一个质数
        {
            vis[i] = i;
            pri[++ cnt] = i;
            phi[i] = i - 1;//质数的欧拉函数等于该质数减1
        }
        for (int j = 1;j <= cnt && i * pri[j] <= n;j ++)//枚举已经得到了的质数
        {
            vis[i * pri[j]] = pri[j];//这个数的最小质因数为第j个质数
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];//上述的第一种情况
                break;
            }
            phi[i * pri[j]] = phi[i] * phi[pri[j]];//上述的第二种情况
            //也可以写作phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
    return;
}