本文转载（或修改）自 OI-Wiki

欧拉函数及有关定理

定义

欧拉函数（Euler's totient function），即 \(\varphi(n)\)，表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。

比如说 \(\varphi(1) = 1\)。

当 \(n\) 是质数的时候，显然有 \(\varphi(n) = n - 1\)。

性质

• 欧拉函数是积性函数。

  即对任意满足 \(a \bot b\) 的整数 \(a,b\)，有 \(\varphi(ab) = \varphi(a)\varphi(b)\)。

  特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(n)\)。

• \(n = \sum_{d \mid n}{\varphi(d)}\)。

可以这样考虑：如果 \(\gcd(k, n) = d\)，那么 \(\frac{k}{d}\bot\frac{n}{d}, ( k < n )\)。

如果我们设 \(f(x)\) 表示 \(\gcd(k, n) = x\) 的数的个数，那么 \(n = \sum_{i = 1}^n{f(i)}\)。

根据上面的证明，我们发现，\(f(x) = \varphi(\frac{n}{x})\)，从而 \(n = \sum_{d \mid n}\varphi(\frac{n}{d})\)。注意到约数 \(d\) 和 \(\frac{n}{d}\) 具有对称性，所以上式化为 \(n = \sum_{d \mid n}\varphi(d)\)。

• 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。 （根据定义可知）

• 设 \(p\) 为任意质数，那么 \(\varphi(p^k)=p^{k-1}\times(p-1)\)。

• 由唯一分解定理，设 \(n = \prod_{i=1}^{s}p_i^{k_i}\)，其中 \(p_i\) 是质数，有 \(\varphi(n) = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}}\)。

实现

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。

实现

int getphi(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);
    return ans;
}

如果是多个数的欧拉函数值，可以利用线性筛法来求得。

• 在 \(i\) 是质数时，根据欧拉函数性质，小于质数 \(i\) 的正整数都与 \(i\) 互质，所以 \(\varphi(i) = i - 1\)。

• 当 \(i\) 能被质数 \(j\) 整除时，\(i \times j\) 包含了 \(i\) 的所有质因子，此时 \(\varphi(i \times j) = \varphi(i) \times j\) 。

• 当 \(i\) 不能被质数 \(j\) 整除时，\(i\) 与 \(j\) 互质，根据欧拉函数的积性，\(\varphi(i \times j) = \varphi(i) \times \varphi(j)\)。

实现

#include <vector>
using namespace std;
const int N = 1000005; // 根据实际需求调整N的大小
vector<int> prime;
int phi[N];
void getphi(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!phi[i])
        {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (int j : prime)
        {
            if (i * j > n) break;
            if (i % j == 0) {
                phi[i * j] = phi[i] * j;
                break;
            }
            phi[i * j] = phi[i] * phi[j];
        }
    }
}

应用

欧拉函数常常用于化简一列最大公约数的和。国内有些文章称它为 欧拉反演

在结论

\[ n=\sum_{d|n}\varphi(d) \]

中代入 \(n=\gcd(a,b)\)，则有

\[ \gcd(a,b) = \sum_{d|\gcd(a,b)}\varphi(d) = \sum_d [d|a][d|b]\varphi(d), \]

其中，\([\cdot]\) 称为 Iverson 括号，只有当命题 \(P\) 为真时 \([P]\) 取值为 \(1\)，否则取 \(0\)。对上式求和，就可以得到

\[ \sum_{i=1}^n\gcd(i,n)=\sum_{d}\sum_{i=1}^n[d|i][d|n]\varphi(d)=\sum_d\left\lfloor\frac{n}{d}\right\rfloor[d|n]\varphi(d)=\sum_{d|n}\left\lfloor\frac{n}{d}\right\rfloor\varphi(d). \]

这里关键的观察是 \(\sum_{i=1}^n[d|i]=\lfloor\frac{n}{d}\rfloor\)，即在 \(1\) 和 \(n\) 之间能够被 \(d\) 整除的 \(i\) 的个数是 \(\lfloor\frac{n}{d}\rfloor\)。

利用这个式子，就可以遍历约数求和了。需要多组查询的时候，可以预处理欧拉函数的前缀和，利用数论分块查询。

GCD SUM

给定 \(n\le 100000\)，求

\[\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\]

仿照上文的推导，可以得出

\[ \sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) = \sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor^2\varphi(d). \]

此时需要从 \(1\) 遍历到 \(n\) 求欧拉函数，用线性筛做就可以 \(O(n)\) 得到答案。

实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXN = 1e5 + 10;
ll ans, n, phi[MAXN], pri[MAXN], cnt;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    phi[1] = 1;
    for (ll i = 2; i <= n; i++)
    {
        if (!phi[i])
        {
            pri[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
        {
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
    for (ll i = 1; i <= n; i++)
        ans += (n / i) * (n / i) * phi[i];
    cout << ans;
    return 0;
}

欧拉定理

与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：

Note

若 \(a \bot m\)，则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\)。

扩展欧拉定理

当然也有扩展欧拉定理，用于处理一般的 \(a\) 和 \(m\) 的情形。

\[ a^b\equiv \begin{cases} a^{b\bmod\varphi(m)},\,&\gcd(a,\,m)=1\\ a^b,&\gcd(a,\,m)\ne1,\,b<\varphi(m)\\ a^{b\bmod\varphi(m)+\varphi(m)},&\gcd(a,\,m)\ne1,\,b\ge\varphi(m) \end{cases} \pmod m \]