欧拉函数

· · 个人记录

欧拉函数

\varphi(N) = \prod_{p | N} {(1 - \frac{1}{p})}

扩展欧拉定理

a^{b} = \begin{cases}a^{b \% \varphi(p)} \qquad \! gcd(a, p) = 1\\ a^{b} \qquad \quad \ \ \ \ \! gcd(a, p) \neq 1, b < \varphi(p) & (mod \ p)\\a^{b \% \varphi(p) + p} \quad \! gcd(a, p) \neq 1, b \ge \varphi(p)\end{cases}

扩展欧拉定理一般用于不可解高次同余方程降次。如 2^{2^{2^{...}}} \pmod{p} 。

线性筛

线性筛筛素数的思想同样能运用到筛欧拉函数，与此同时，也能用于筛约数个数、约数和等。

int euler() {
    for (int i = 2; i <= n; ++i) {
        if (!v[i])
            v[i] = i, prime[++total] = i, phi[i] = i - 1;
        for (int j = 1; j <= total && i * prime[j] <= n; ++j) {
            if (prime[j] > v[i])
                break;
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
        }
    }
}