质数，约数，欧拉函数，快速幂
题单介绍
## 质数
质数是大于1的自然数，且仅能被1和自身整除的数。例如，2、3、5、7、11等都是质数。质数在数论中具有重要地位，因为它们是自然数的基本构建块，任何一个大于1的自然数都可以唯一分解为质数的乘积，这称为质因数分解。
## 约数
约数是指能够整除某个整数的数。比如，12的约数有1、2、3、4、6和12本身。一个数的约数可以通过其质因数分解来计算。例如，如果一个数的质因数分解为
$$
p_1^{e_1} \times p_2^{e_2} \times \ldots \times p_n^{e_n}
$$
则它的约数总数为
$$
(e_1 + 1)(e_2 + 1) \ldots (e_n + 1)
$$
## 欧拉函数
欧拉函数（Euler's Totient Function），通常记作 $\phi(n)$，表示小于或等于 $n$ 的正整数中与 $n$ 互质的整数的数量。例如，$\phi(12) = 4$，因为小于12的与12互质的数是1、5、7和11。对于质数 $p$，有 $\phi(p) = p - 1$；对于
$$
n = p_1^{e_1} \times p_2^{e_2} \times \ldots \times p_k^{e_k}
$$
的情况，欧拉函数的计算公式为：
$$
\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \ldots \left(1 - \frac{1}{p_k}\right)
$$
## 快速幂
快速幂是一种高效计算 $a^b \mod m$ 的算法，尤其适用于大数的幂运算。其基本思想是利用二进制表示法，将指数 $b$ 转换为二进制，然后通过平方和乘法来减少乘法的次数。具体步骤如下：
1. 将 $b$ 转换为二进制。
2. 从最低位开始，若该位为1，则将当前结果乘上 $a$。
3. 每次将 $a$ 平方，同时将指数右移一位。
这种方法的时间复杂度为 $O(\log b)$，相较于直接计算 $a^b$ 的 $O(b)$ 有显著提高。