【提高】类欧几里得算法基础

训练指导

征求题目,有意者私信。

感谢名单:

由于讲解可以放在后面,于是训练指导就放在前面了。

所以可以发现其实很多类欧都存在二分的情况。

类欧教程详解

介绍了 f 函数的化简,以及化简相关的一些 Trick 和 Conclusion。

介绍了 gh 函数的化简,给出了代码实现以及更详细的介绍。

整合前两部分,衔接处作了简单修改,投稿至题解区。

一道处处透着类欧气息的分类讨论数学题。


  1. P4132 - [BJOI2012] 算不出的等式
  2. P5170 - 【模板】类欧几里德算法
  3. CF1098E - Fedya the Potter
  4. CF1182F - Maximum Sine
  5. P5171 - Earthquake
  6. P5172 - [清华集训 2014] Sum
  7. P5179 - Fraction
  8. P4433 - [COCI 2009/2010 #1] ALADIN