欧拉函数

欧拉函数

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

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

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

利用唯一分解定理，我们可以把一个整数唯一地分解为质数幂次的乘积。

设 $n = \prod_{i=1}^{n}p_i^{k_i}$ ，其中 $p_i$ 是质数，那么 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$ 。

欧拉定理

若 $\gcd(a, m) = 1$ ，则 $a^{\varphi(m)} \equiv 1 \pmod{m}$ 。

费马小定理

若 $p$ 为素数， $\gcd(a, p) = 1$ ，则 $a^{p - 1} \equiv 1 \pmod{p}$ 。

威尔逊定理

$(p-1)!\equiv-1\pmod{p}$

若 $p$ 为质数，则 $p$ 可整除 $(p-1)!+1$ 。

筛法求欧拉函数

void phi_table()
{
    for (int i = 1; i < maxn; i++) {
        phi[i] = i;
    }
    for (int i = 2; i < maxn; i++) {
        if (phi[i] == i) {
            for (int j = i; j < maxn; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

Pollard Rho 算法求欧拉函数

ll get_phi(int n)
{
    ll res = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            n /= i;
            res *= i - 1;
            while (n % i == 0) {
                n /= i;
                res *= i;
            }
        }
    }
    if (n > 1) {
        res *= n - 1;
    }
    return res;
}