欧拉函数和欧拉降幂

欧拉函数

将 $\varphi(x)$ 表示为小于 x 并且与 x 互素的正整数个数
$$
x = a_1^{b_1} \cdot a_2^{b_2} \cdot a_3^{b_3} \cdots a_n^{b_n}
$$
其中 $a_1, a_2, a_3, \cdots, a_n$ 是一组质数。

可得
$$
\varphi(x) = (a_1 - 1) \cdot a_1^{b_1 - 1} \cdot (a_2 - 1) \cdot a_2^{b_2 - 1} \cdots (a_n - 1) \cdot a_n^{b_n - 1}
$$

$$
\varphi(x) = x \cdot \left(1 - \frac{1}{a_1}\right) \left(1 - \frac{1}{a_2}\right) \cdots \left(1 - \frac{1}{a_n}\right)
$$

int euler(int x) {    
    int res = x;  
    for (int i = 2; i * i <= x; i++) {  
        if (x % i == 0) {  
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;  
        }  
    }  
    if (x > 1) res = res / x * (x - 1);  
    return res;  
}  

欧拉降幂

若
$$
\gcd(a, n) = 1
$$
根据欧拉定理
$$
a^{\varphi(n)} \equiv 1 \pmod{n}
$$

所以
$$
a^b \pmod{n} \equiv a^{t \cdot \varphi(n) + r} \pmod{n} \equiv a^r \pmod{n}
$$

如果 $\gcd(a, n) \neq 1$，则 $r = b \pmod{n}$
$$
a^b \pmod{n} \equiv a^{r + \varphi(n)} \pmod{n}
$$

当 b 特别大的时候使用。