欧拉函数与欧拉定理

题单介绍

## 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))

题目列表

  • [NOIP2012 提高组] 同余方程
  • 【模板】有理数取余
  • [SDOI2008]仪仗队
  • [SDOI2012] Longge 的问题
  • 【模板】扩展欧拉定理
  • [HAOI2012]外星人
  • 上帝与集合的正确用法
  • [SDOI2015]约数个数和
  • GCD
  • 【模板】杜教筛(Sum)
  • Power Tower
  • [六省联考 2017] 相逢是问候
  • [Ynoi2016] 炸脖龙 I