类欧几里得算法学习笔记

常见的用类欧几里得算法处理的几个函数:

并定义:

可在 $O(\log \min(a, b))$ 的时间内计算以上函数。

函数 $f$ 的处理

当 $a \geq c$ 或 $b \geq c$ 时:

当 $a < c$ 且 $b < c$ 时:

函数 $g$ 的处理

当 $a \geq c$ 或 $b \geq c$ 时:

当 $a < c$ 且 $b < c$ 时:

函数 $h$ 的处理

当 $a \geq c$ 或 $b \geq c$ 时:

当 $a < c$ 且 $b < c$ 时: