欧拉函数（Euler's function）即 $\phi (n)$，表示 $1$ 至 $n-1$ 中与 $n$ 互质的数的个数。

例如 $\phi (10)=4$，因为 $1,3,7,9$ 都是与 $10$ 互质的数。

特别地，当 $n$ 为质数时，$\phi (n)=n-1$。

欧拉函数的性质

1. 当 $n$ 是质数时，对于 $n=p^k$，有 $\phi (n)=p^k-p^{k-1}=p^{k-1}(p-1)$。

证明：比 $p^k$ 小的正整数共有 $p^{k-1}$ 个（例如 $p,2p,3p,\dots p^k-p$），而其中能被 $p$ 整除的有 $p^{k-1}-1$ 个，两者做差即可得到。

2. 对任意满足 $gcd(a,b)=1$ 的整数 $a,b$，有 $\phi (a\cdot b)=\phi (a)\cdot \phi (b)$。

证明：在 $1\sim ab$ 中，既与 $a$ 互质，也与 $b$ 互质的数才可以与 $ab$ 互质，而 $a$ 和 $b$ 没有公因子，因而这样的数共有 $\phi (a)\phi (b)$ 个。

3. 对于质数 $p$，若 $n\mathrm{\%}p=0$，则 $\phi (n\cdot p)=\phi (n)\cdot p$，若 $n\mathrm{\%}p\ne 0$，则 $\phi (n\cdot p)=\phi (n)\cdot (p-1)$。

4. 对于 $n>1$，$1\sim n$ 中与 $n$ 互质的数的和等于 $n\cdot \phi (n)/2$。

5. $\sum _{d|n}\phi (d)=n$。

欧拉函数朴素求解方法

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        
        int ans = n;
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) {
                // ans = ans * (1 - 1 / i);
                ans = ans / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) ans = ans / n * (n - 1);
        cout << ans << endl;
    }
    
    return 0;
}

筛法求解欧拉函数

依据性质 $3$ 再结合欧拉筛，可使用复杂度为 $O(n)$ 算法求解欧拉函数。

int phi[N], prime[N], st[N], tot;

void eular(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        
        for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}