欧拉函数与欧拉定理
题单介绍
## Part 1 简述
欧拉函数 $\varphi(x)$ 表示不大于 $x$ 的整数中与 $x$ 互质的数的个数。它是常见的积性函数，常利用其定义解题，也常用于反演：$\varphi * 1=Id$。
欧拉定理的描述为当 $(a,p)=1$ 时，$a^{\varphi(p)} \equiv 1 \pmod p$。可以用于乘法逆元的求解、降幂等。费马小定理是其特殊形式。
扩展欧拉定理的描述为当 $b>=\varphi(p)$ 时，$a^b \equiv a^{b \mod \varphi(p)+\varphi(p)} \pmod p$，可以用于降幂等。
## Part 2 题目
- P1082 同余方程（欧拉定理/费马小定理求单个数逆元）
- P2613 【模板】有理数取余（求逆元分数取余）
- P2158 [SDOI2008]仪仗队（欧拉函数定义与线性筛）
- P2303 [SDOI2012]Longge的问题（数论分块与欧拉函数定义）
- P5091 【模板】扩展欧拉定理（扩展欧拉定理模板）
- P2350 [HAOI2012]外星人（运用欧拉函数性质）
- P4139 上帝与集合的正确用法（扩展欧拉定理类模板）
- P3327 [SDOI2015]约数个数和（一个结论+欧拉函数反演）
- P2568 GCD（欧拉函数反演）
- P4213 【模板】杜教筛（Sum）（欧拉函数非线性筛法，但注意要与莫比乌斯函数同筛，需要一定反演知识）
- CF906D Power Tower（扩展欧拉定理较难类模板）
- P3747 [六省联考2017]相逢是问候（线段树+扩展欧拉定理）
- P3934 Nephren Ruq Insania（2020.5.17 新增 感谢 [bovine__kebi](https://www.luogu.com.cn/user/294736)）