其实我原来是把欧拉函数和欧拉定理写在一篇博客里的，但是后来发现欧拉函数特别常用，然后总去那里找也不方便，于是就把它单独分出来了。

欧拉函数 $\varphi(n)$：对于正整数 $n$，欧拉函数是不大于 $n$ 的正整数中与 $n$ 互质的数的数目。

通式：$\varphi(n)=x\prod_{i=1}^n\left(1-\frac{1}{p_i}\right)$，其中 $p_1,p_2,\cdots,p_n$ 为 $x$ 的所有质因子，$x$ 是不为 $0$ 的整数，$\varphi(1)=1$。
注意：只取不同的质因数。例如 $12=2\times 2\times 3$，那么 $\varphi(12)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=4$。

欧拉函数的一些性质：
若 $n=p^k$，$p$ 为质数，$\varphi(n)=p^k-p^{k-1}=(p-1)p^{k-1}$；
若 $m,n$ 互质，$\varphi(mn)=\varphi(m)\varphi(n)$；
若 $n$ 为奇数，$\varphi(2n)=\varphi(n)$；
若 $n$ 为质数，$\varphi(n)=n-1$，此时的欧拉定理即为费马小定理。

算法实现与分析：
求解 $\varphi(n)$ 需要对 $n$ 进行素因子分解。
(1) 直接实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
int phi(int n)
{
    int rea = n;
    for (int i = 2; i <= n; ++i)
        if (n % i == 0)
        {
            rea = rea - rea / i;
            do
                n /= i;
            while (n % i == 0);
        }
    return rea;
}

由分析知，这个函数的复杂度为 $O(n)$，如果 $n$ 达到 1 000 000 000，肯定会超时。
由于任何一个合数都至少有一个不大于 $\sqrt{n}$ 的素因子，所以只需要遍历到 $\sqrt{n}$ 即可，这样复杂度降低为 $O(\sqrt{n})$。
下面是优化代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int phi(int n)
{
    int rea = n;
    for (int i = 2, i * i <= n; ++i)
        if (n % i == 0)
        {
            rea = rea - rea / i;
            do
                n /= i;
            while (n % i == 0);
        }
    if (n > 1)
        rea = rea - rea / n;
    return rea;
}

(2) 素数表实现：
先把 50 000 以内的素数用筛法选出来并保存，以方便欧拉函数使用，这里采用埃拉托斯尼斯筛法。
这样，若不考虑筛法的时间复杂度，而单纯看欧拉函数，其复杂度变为 $O(x)$，$x$ 为 $\sqrt{n}$ 以内素数的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N = 50001;
bool isprime[N];
int prime[N], nprime; // 下标从 1 开始
void doprime(void) // 埃拉托斯尼斯筛法
{
    nprime = 0;
    memset(isprime, true, sizeof(isprime));
    isprime[1] = 0;
    for (long long i = 2; i < N; ++i)
        if (isprime[i])
        {
            prime[++nprime] = i;
            for (long long j = i * i; j < N; j += i)
                isprime[j] = false;
        }
}
int phi(int n)
{
    int rea = n;
    for (int i = 1; prime[i] * prime[i] <= n; ++i) // 对于一些不是素数的可不用遍历
        if (n % prime[i] == 0)
        {
            rea = rea - rea / prime[i];
            do
                n /= prime[i];
            while (n % prime[i] == 0);
        }
    if (n > 1)
        rea = rea - rea / n;
    return rea;
}

(3) 递推求欧拉函数：
如果频繁地要使用欧拉函数值，就需要预先打表。下面介绍递推求欧拉函数的方法。
可预先置所有数的欧拉函数值都为它本身，如果 $p$ 是一个正整数且满足 $\varphi(p)=p-1$，那么 $p$ 是素数，在遍历过程中如果遇到欧拉函数与自身相等的情况，那么说明该数为素数，把这个数的欧拉函数值改变，同时也把能被该素因子整除的数改变。其复杂度约为 $O(n\ln n)$。
1
2
3
4
5
6
7
8
for (int i = 1; i <= maxn; ++i)
    phi[i] = i;
for (int i = 2; i <= maxn; i += 2)
    phi[i] /= 2;
for (int i = 3; i <= maxn; i += 2)
    if (phi[i] == i)
        for (int j = i; j <= maxn; j += i)
            phi[j] = phi[j] / i * (i - 1);

maxn 是待求欧拉函数值的数的最大值，phi 数组存储欧拉函数值。