欧拉算法集锦——在欧气和欧皇间，我选择了（）

## 0b0000：前言

~~欸话说这是哪个唐诗**欧拉**筛取的这个标题？~~

本人将按难度升序排序，依次讲述有关欧拉的各类算法，希望大家能喜欢。（手动狗头）

## 0b0001：欧拉筛

### 介绍

欧拉筛是一种高效的素数筛法，能在 $\Theta(n)$ 的时间复杂度内筛出小于等于 $n$ 的素数，相比于大家比较常用的埃氏筛（时间复杂度 $\Theta(n \log n)$），欧拉筛减少了一些不必要的计算，增加了一些效率。

### 原理

我们定义两个数组 `not_prime[]` 和 `primes[]`。第一个数组存储某一个数是否为素数（不是标记为 $1$，否则为 $0$），而第二个数组存储目前筛到的素数。

过程如下：

- 定义变量 $i$，从 $2$ 遍历到 $n$，每一次遍历执行下述操作：
- - 如果 $i$ 被标记成了素数，将 $i$ 加到质数列表 `primes[]`。
  - 在所有情况下，遍历小于等于 $n$ 的 $primes_j \times i$，并将其标记为非素数（合数）。

欧拉筛的核心思想，就是将现存的素数跟当前遍历到的数相乘，去掉可以表示为两个大于 $1$ 的自然数之积的数。

### 代码

```cpp
void Shai(int n){
	not_prime[0] = not_prime[1] = true; //0 和 1 不是素数 
	
	for(int i = 2; i <= n; ++i){
		if(!not_prime[i]) primes.push_back(i); //是素数，加入素数列表里面 
		for(int j = 0; primes[j] * i <= n; ++j){
            not_prime[primes[j] * i] = true; 
			if(i % primes[j] == 0) break; //如果发现 i 里面含有 primes[j]，提前跳出循环，因为 i 乘其他素数也一定会被 primes[j] 的倍数给筛掉，不用在这里多筛一次
		} 
	}
} 
```

### 练习题

- [P3383 【模板】线性筛素数](https://www.luogu.com.cn/problem/P3383)，这是一道模板题。
- [P1217 \[USACO1.5\] 回文质数 Prime Palindromes](https://www.luogu.com.cn/problem/P1217)，这一道题是模板筛法的小拓展。
- [P1865 A % B Problem](https://www.luogu.com.cn/problem/P1865)，这一道题需要结合前缀和来解，略微偏难。

### 扩展用法

欧拉筛可以求各种积性函数（定义下一章有），包括莫比乌斯函数 $\mu (n)$，以及我们下一章要讲解的欧拉函数 $\varphi(n)$。

这里给大家讲解一下莫比乌斯函数 $\mu(n)$ 如何使用欧拉筛求解。仅供各位大佬拓展。

---

首先了解一下莫比乌斯函数的定义：
我们假设 $p$ 是 $n$ 的最小质因子，并且令 $\dfrac{n}{p} = n'$，则：

$$
\mu(n) = \begin{cases}
0 & n' \equiv 0 \pmod p \\
-1 & n \in \text{prime} \\
-\mu(n') & \text{otherwise}
\end{cases}
$$

#### 求解过程

首先按照正常的欧拉筛法筛素数，不过这次需要加上记录莫比乌斯函数值的数组 `mu[]`。初始化所有 $\mu(i) = 1$

根据定义可以看出 $n$ 为素数的时候，$\mu(n) = -1$，所以筛到了质数，就将其莫比乌斯函数值设为 $-1$ 即可。\
由于 $n' \equiv 0 \pmod p$，所以 $n\ |\ p^2$。所以如果被筛数为 $i$，在 $i\ |\ primes_j$ 的情况下，需要设置 $\mu(i\times primes_j) = 0$（以及跳出循环），否则 $\mu(i\times primes_j) \gets -\mu(i)$。

#### 代码

```cpp
void Shai(int n){
	not_prime[0] = not_prime[1] = true; //0 和 1 不是素数 
	memset(mu, -1, sizeof(mu)); 
	for(int i = 2; i <= n; ++i){
		if(!not_prime[i]) primes.push_back(i), mu[i] = -1; //是素数，加入素数列表里面 
		for(int j = 0; primes[j] * i <= n; ++j){
            not_prime[primes[j] * i] = true; 
			if(i % primes[j] == 0) {mu[i * primes[j]] = 0; break};
			mu[i * primes[j]] = -mu[i];
        }
	}
} 
```

这样子你就可以完成：

- [B4308 \[蓝桥杯青少年组国赛 2024\] 第三题](https://www.luogu.com.cn/problem/B4308)

（~~里面还有我的题解哦但是用埃氏筛写的。~~）

## 0x0010：欧拉函数

### 表示

$\varphi(n)$。$\LaTeX$ 中的渲染方法为 `\varphi(n)`。

### 定义

$\varphi(n)$ 表示：在 $[1,n]$ 区间内，与 $n$ 互质的正整数个数。

### 性质

- 欧拉函数是积性函数，即当 $\gcd(x,y) = 1$ 时，$\varphi(x) \times \varphi(y) = \varphi(xy)$。
- 当 $x$ 为质数时，$\varphi(x) = x - 1$。
- 若 $x = p^t$，则 $\varphi(x) = p^t - p^{t-1}$。

### 计算

#### 方法一：暴力法

暴力计算 $\sum_{i=1}^{n}[\gcd(i,n)=1]$。其中的方括号为艾弗森括号，括号内的式子成立，值为 $1$，否则为 $0$。代码省略。

时间复杂度 $\Theta(n \log n)$，原因：一次求 $\gcd$ 是 $\Theta(\log n)$ 的，而需要 $n$ 次枚举。

---

#### 方法二：质因数分解法

我们假设 $n$ 能分解为如下形式：

$$
n = p_1^{t_1} \times p_2^{t_2} \times \cdots \times p_k^{t_k}
$$

其中 $\forall p_i \in \text{prime}$ 且 $\forall t_i \in \N^{ * }$。

那么：

$$
\varphi(n) = n\prod_{i=1}^{k} \dfrac{p_i - 1}{p_i}
$$

代码：

```cpp
int phi(int x){
	int ans = x; //初始化
	for(int i = 2; i * i <= x; ++i){
		if(x % i == 0){ //存在该质因数
			while(x % i == 0) x /= i; //将所有质因数给除完
			ans /= i;
			ans *= (i - 1); //等价于乘上 (i - 1) / i，也就是计算上式的其中一项
		} 
	} 
	if(x > 1)
		ans /= x, ans *= (x - 1); //出现剩余特判
	return ans; 
} 
```

时间复杂度 $\Theta(\sqrt{n})$，等同于朴素分解质因数的复杂度，证明略。

**正确性证明**：

根据性质 $3$ 可知，当 $p$ 为任意数时，$\varphi(p^t) = p^{t-1} \times(p-1)$，因式分解易证。

根据欧拉函数的积性，我们可以知道：

$$
\varphi(n) = \prod^{k}_{i=1} \varphi(p_i^{t_i})
$$

代入 $\varphi(p^t) = p^{t-1} \times(p-1)$，得：

$$
\varphi(n) = \prod_{i=1}^{k} p_i^{t_i-1} \times(p_i-1)
$$

对于每一项，把 $p_i^{t_i-1}$ 乘上 $p_i$，再把 $p_i-1$ 除以 $p_i$，得：

$$
\varphi(n) = \prod_{i=1}^{k} p_i^{t_i} \times \frac{p_i-1}{p_i}
$$

因为 $n = p_1^{t_1} \times p_2^{t_2} \times \cdots \times p_k^{t_k}$，根据乘法结合律，可以把 $\prod p_i^{t_i}$ 从原式中提取出来得到 $n$，故：

$$
\varphi(n) = n\prod_{i=1}^{k} \dfrac{p_i - 1}{p_i}
$$

证毕。

证明过程来源于 [OI Wiki](https://oiwiki.com/math/number-theory/euler-totient/)，稍微加上了一点自己的理解。

#### 方法三：欧拉筛法

欧拉筛计算欧拉函数，这非常合理！\
这种方法一般适用于求一个或多个区间内的欧拉函数值，时间复杂度为 $\Theta(n)$。

原理大概是方法二和欧拉筛的结合，这里就不多赘述。

```cpp
void Shai(int n){
	phi[1] = 1; 
	for(int i = 2; i <= n; ++i){
		if(!vis[i]){
			primes[cnt++] = i;
			phi[i] = i - 1; 
		} 
		for(int j = 0; prime[j] * i <= n; ++j){
			int k = primes[j] * i; vis[k] = true;
			if(i % primes[j] == 0){
				phi[k] = phi[i] * primes[j];
				break; 
			} 
			phi[k] = phi[i] * (primes[j] - 1); //这里套了刚才的公式
		} 
	} 
} 
```

### 练习题

- [P12216 \[蓝桥杯 2023 国 Java B\] 互质](https://www.luogu.com.cn/problem/P12216)

~~好吧我承认这里面也有我写的题解。~~

## 0x0011：欧拉定理

### 内容

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

实际上，欧拉定理是费马小定理的一般形式，能证明欧拉定理，费马小定理自然得证。

### 证明

- 我们不妨假设 $r_1,r_2,\cdots,r_{\varphi(m)}$ 是模 $m$ 意义下的一个简化剩余系。也就是说，**对于任意的 $i$，有 $\gcd(r_i,m) = 1$；对于任意的 $i\ne j$，有 $r_i\not\equiv r_j \pmod m$**。
- 将每一个元素都乘上 $a$，由于 $\gcd(a,m) = 1$，所以易证 $a\cdot r_1,a\cdot r_2,\cdots,a\cdot r_{\varphi(m)}$ **也是模 $m$ 的简化剩余系**。（因为如果 $a\cdot r_i \equiv a\cdot r_j \pmod m$，那么由于 $a,m$ 互质，消掉两边的 $a$ 会得到 $r_i \equiv r_j$，与原假设矛盾）
- 这个时候，将两个序列中的元素分别相乘，不难发现它们模 $m$ 意义下是同余的，即：
  $$
  \prod_{i=1}^{\varphi(m)} r_i \equiv \prod_{i=1}^{\varphi(m)} (a\cdot r_i) \pmod m
  $$
- 将同余号右边的 $\varphi(m)$ 个 $a$ 从求积符号中提出来，得：
  $$
  \prod_{i=1}^{\varphi(m)} r_i \equiv a^{\varphi(m)}\prod_{i=1}^{\varphi(m)} r_i \pmod m
  $$
- 因为 $\prod r_i$ 是和 $m$ 互质的，因此可以从同余式中消掉。故：
  $$
  1 \equiv a^{\varphi(m)} \pmod m
  $$

原命题得证。

## 0x0100：扩展欧拉定理

### 内容

设 $a,b,m$ 为正整数，则：

$$
a^b \equiv \begin{cases}
a^b \pmod m & b < \varphi(m) \\
a^{b \bmod \varphi(m) + \varphi(m)} \pmod m & b \ge \varphi(m)
\end{cases}
$$

### 证明

分多种情况讨论。

#### 情况一：$b < \varphi(m)$

~~如果不会证这个建议重修幼儿园数学（不是）。~~

#### 情况二：$b > \varphi(m),\gcd(a,m) = 1$

套普通欧拉定理就行，~~你们自己证吧我跑了~~。

---

接下来的两种情况，我们需要对 $a$ 分解质因数，假设其为如下形式：

$$
a = p_1^{t_1} \times p_2^{t_2} \times \cdots p_k^{t_k}
$$

现在问题等价于：$a$ 的每个质因子 $p_i$ 满足原条件就行。\
为啥？因为保证 $a\equiv b \pmod x$ 且 $a\equiv b \pmod y$ 必须要满足 $a\equiv b \pmod {\operatorname{lcm}(x,y)}$，能用 CRT 证。根据这个定理对质因子进行合并就行。

显然这个时候要么 $m\ |\ p_i$，要么 $\gcd(m,p_i) = 1$。

---

#### 情况三：$\gcd(m,p_i) = 1$

仍然是套普通欧拉定理~~所以我再跑~~。

$$
a^b \equiv a^{\lfloor\frac{b}{\varphi(m)}\rfloor \varphi(m) + b \bmod \varphi(m)} \equiv a^{b \bmod \varphi(m)} \pmod {p_i^{t_i}}
$$

#### 情况四：$m\ |\ p_i$

不水了不水了，讲正经的。

---

首先需要插播一条欧拉函数的性质：若 $x = p^k$，则 $\varphi(x) = p^k - p^{k-1}$。\
所以这个时候 $\varphi(p_i^{t_i}) = p_i^{t_i} - p_i^{t_i - 1} = p_i^{t_i - 1}(p_i - 1)$。

由于：

$$
\varphi(m) \ge \varphi(p_i^{t_i}) = p_i^{t_i - 1}(p_i - 1) \ge t_i
$$

故：

$$
b\ge \varphi(m) \ge t_i
$$

进一步得出：

$$
a^b \equiv 0 \pmod {p_i^{t_i}}
$$

因为 $a,m$ 里面存在因子 $p_i$，而 $b \ge t_i$。同理，指数为 $b \bmod \varphi(m) + \varphi(m)$ 时，因为 $b\bmod \varphi(m) \ge 0$，所以 $b\bmod \varphi(m) + \varphi(m) \ge \varphi(m)\ge t_i$。所以：

$$
a^{b\bmod \varphi(m) + \varphi(m)} \equiv 0 \pmod {p_i^{t_i}}
$$

两个同余式的左边一坨都和 $0$ 同余，故：

$$
a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod{p_i^{t_i}}
$$

---

由于 $a,b$ 对于 $m$ 的每个质因子 $p_i$ 都满足定理条件，将每个条件合并得：

$$
a^b\equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m
$$

综上，原定理成立。

### 练习题

扩展欧拉定理一般来说是求指数特别大的 $a^b \bmod m$ 的结果。（例如 $b = 10^{100}$，这么大的数存不下，只能将指数取模）给大家推荐一点练习题：

- [P5091 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)，这是一道模板题。
- [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139)，这道题求的是 $2^{2^{2^{\cdots}}} \bmod p$ 的值，可以使用扩展欧拉定理，将**无穷**变成**有穷**。

## 0b0101：欧拉公式

### 内容

注意：此处的 $i$ 为虚数单位，$i^2=-1$，而 $e$ 为自然常数，为自然对数 $\ln$ 的底数，$e = \lim_{n \to \infty}(1 + \dfrac{1}{n})^n$。

欧拉公式的一般形式为：

$$
e^{ix} = \cos(x) + i\sin(x)
$$

令 $x = \pi$，可以得到：

$$
e^{i\pi} = -1
$$

这个公式将数学中五个基本常数 $0,-1,\pi,e,i$ 结合到一起，简洁而有用，因此在数学中声誉极大，称作“欧拉恒等式”，也被誉为“上帝公式”。\
而普通的欧拉公式也有很大用处，在复分析领域中有不可估量的功劳。

### 证明

欧拉公式的证明有多种方式，这里采用较为简单的级数证明法。

首先对 $\cos(x),\sin(x),e^x$ 进行泰勒展开：

$$
\cos(x) = \frac{x^0}{0!} + \frac{x^2}{2!} - \frac{x^4}{4!} + \frac{x^6}{6!} - \cdots
$$

$$
\sin(x) = \frac{x^1}{1!} - \frac{x^3}{3!} + \frac{x^5}{5} - \frac{x^7}{7!} + \cdots
$$

$$
e^x = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots
$$

这个时候，将 $e^x$ 替换成 $e^{ix}$，可以得到：

$$
\tag{0}e^{ix} = \frac{(ix)^0}{0!} + \frac{(ix)^1}{1!} + \frac{(ix)^2}{2!} + \frac{(ix)^3}{3!} + \cdots
$$

我们把 $e^{ix}$ 每一项的分子展开，得到：

$$
\begin{align}
 &e^{ix} \\
 =&\ \frac{i^0x^0}{0!} + \frac{i^1x^1}{1!} + \frac{i^2x^2}{2!} + \frac{i^3x^3}{3!} + \frac{i^4x^4}{4!} + \frac{i^5x^5}{5!} +\frac{i^6x^6}{6!} + \frac{i^7x^7}{7!}\cdots \\
 =&\ \frac{x^0}{0!} + \frac{ix^1}{1!} - \frac{x^2}{2!}-\frac{ix^3}{3!} + \frac{x^4}{4!} + \frac{ix^5}{5!} - \frac{x^6}{6!}-\frac{ix^7}{7!} + \cdots \\
 =&\ (\frac{x^0}{0!} + \frac{x^2}{2!} - \frac{x^4}{4!} + \frac{x^6}{6!} - \cdots) + (\frac{ix^1}{1!} - \frac{ix^3}{3!} + \frac{ix^5}{5} - \frac{ix^7}{7!} + \cdots) \\
 =&\ (\frac{x^0}{0!} + \frac{x^2}{2!} - \frac{x^4}{4!} + \frac{x^6}{6!} - \cdots) + i(\frac{x^1}{1!} - \frac{x^3}{3!} + \frac{x^5}{5} - \frac{x^7}{7!} + \cdots) \\
 =&\ \cos(x) + i\sin(x)
\end{align}
$$

欸，看到这个过程，你可能有点懵逼，但是没有关系，当时作者也愣了亿下，我们来一步步推导。

首先看到 $(2)$ 式，其实就是把 $(0)$ 式中的 $(ix)^t$ 给展开成了 $i^tx^t$，这一点想必大家都了解。\
再看 $(3)$ 式出现的变化，我们按照如下规律，将 $i$ 的次数减小到了 $1$ 或 $0$：

$$
i^x = \begin{cases}
1 & x \equiv 0 \pmod 4 \\
i & x \equiv 1 \pmod 4 \\
-1 & x \equiv 2 \pmod 4 \\
-i & x \equiv 3 \pmod 4
\end{cases}
$$

其中 $x \in \N^{ * }$。

这一点在复平面上显而易见，毕竟将一个复数向量乘上 $i$ 会使其逆时针旋转 $90$ 度。

那么 $(4)$ 式的变化呢？就是把 $i$ 的次数为 $1$ 的项和次数为 $0$ 的项分离了，这个肯定非常好理解。\
$(5)$ 式的变化也不难，把后面一坨多项式（我不知道要用什么量词了）的公因式 $i$ 提取出来就可以得到了。\
这个时候，大家肯定要震惊：怎么把余弦和正弦函数的泰勒展开式给搞出来了？直接无脑代入！然后原命题就得证了。（没得错！就是这么简单！）

## 0b0110：后记

话说关于欧拉的算法和公式好像还是挺多的，不过蒟蒻作者难免会有些疏忽，会漏掉一些自己没听说过（或者不会）的算法，出现笔误也有可能。也是非常感谢各位巨巨巨巨佬指正或补充，如果能加一个点赞就更好了！同时感谢管理员大大在百忙之中抽空审核我的文章！

正在渲染内容...